Bubble Algoritma Sortir di Java: Program & Contoh Penyortiran Array

Apa itu Bubble Urutkan?

BubbleSort adalah algoritma pengurutan berbasis perbandingan sederhana yang membandingkan elemen pertama dari array dengan elemen berikutnya. Jika elemen saat ini dalam array secara numerik lebih besar daripada elemen berikutnya, elemen-elemen tersebut ditukar. Demikian pula, algoritma akan menelusuri seluruh elemen array.

Algoritma ini dinamakan demikian karena cara nilai terbesar di wilayah yang belum diurutkan secara bertahap naik ke posisi akhirnya, seperti gelembung yang naik ke permukaan air. Setelah putaran pertama selesai, elemen terbesar menempati indeks terakhir. Setelah putaran kedua, elemen terbesar kedua terkunci di tempatnya, dan proses berulang hingga array sepenuhnya terurut.

Dalam artikel ini, kita akan membuat sebuah Java program untuk mengimplementasikan Bubble Urutkan. Periksa output kode yang akan membantu Anda memahami logika program, lalu tinjau versi yang dioptimalkan dan analisis kompleksitas yang menyertainya.

Bagaimana BubblApakah algoritma pengurutan e berfungsi?

BubblAlgoritma Sort bekerja melalui beberapa tahapan berulang pada array. Setiap tahapan berjalan dari indeks pertama hingga akhir wilayah yang belum diurutkan, membandingkan nilai-nilai yang berdekatan dan melakukan pertukaran.ping Mereka akan dipindahkan setiap kali muncul dalam urutan yang salah. Karena nilai terbesar yang tersisa selalu berpindah ke paling kanan dari wilayah yang tidak terurut, wilayah tersebut menyusut tepat satu posisi setelah setiap putaran.

Proses lengkapnya dapat dipecah menjadi empat langkah yang dapat diulang:

1. Bandingkan: Periksa elemen pada indeks j-1 dan bandingkan dengan elemen pada indeks j.
2. Menukar: Jika elemen sebelah kiri lebih besar dari elemen sebelah kanan, tukar kedua nilai tersebut menggunakan variabel sementara.
3. Muka: Geser satu posisi ke kanan dan ulangi hingga mencapai ujung wilayah yang belum diurutkan.
4. Ulangi: Mulailah proses baru pada wilayah yang satu elemen lebih pendek, dan berhenti setelah n-1 proses atau ketika proses tersebut tidak melakukan pertukaran.

Tabel di bawah ini tracIni adalah contoh array {860, 8, 200, 9} yang digunakan dalam program di halaman ini. Ini menunjukkan dengan tepat nilai mana yang menetap di posisi akhirnya pada akhir setiap proses.

Perhatikan bahwa langkah ketiga melakukan perbandingan tetapi tidak melakukan pertukaran. Implementasi yang dioptimalkan mendeteksi kondisi tersebut dan berhenti seketika, yang merupakan peningkatan paling berharga yang dapat Anda terapkan pada algoritma ini.

BubblPseudokode Algoritma Pengurutan e

Sebelum menulis Java Sintaksis membantu mengekspresikan logika dalam pseudocode yang netral terhadap bahasa. Versi di bawah ini menyertakan flag keluar lebih awal, sehingga mencakup perilaku klasik dan yang dioptimalkan.

procedure bubbleSort(array A, integer n)
    for i from 0 to n - 2 do
        swapped := false
        for j from 1 to n - i - 1 do
            // compare the adjacent pair
            if A[j - 1] > A[j] then
                swap A[j - 1] and A[j]
                swapped := true
            end if
        end for
        // no swap in a full pass means the array is sorted
        if swapped = false then
            break
        end if
    end for
end procedure

Loop luar mengontrol jumlah lintasan, dan loop dalam mengontrol perbandingan di dalam satu lintasan. Batas atas loop dalam adalah n – i – 1 karena i posisi terakhir sudah berisi nilai akhirnya.

Java Program untuk Diimplementasikan Bubble Urutkan

Program berikut mengurutkan array bilangan bulat dalam urutan menaik. Pernyataan print tambahan sengaja ditempatkan di dalam loop, karena membaca setiap bagiannya akan memakan waktu. trace adalah cara tercepat bagi pemula untuk memahami bagaimana pertukaran terakumulasi.

package com.guru99;

public class BubbleSort {

    public static void main(String[] args)
    {
        int arr[] = {860, 8, 200, 9};

        System.out.println("---Array BEFORE Bubble Sort---");

        printArray(arr);

        bubbleSort(arr); //sorting array elements using bubble sort

        System.out.println("---Array AFTER Bubble Sort---");

        printArray(arr);

    }

    static void bubbleSort(int[] array)
    {
        int n = array.length;
        int temp = 0;
        for(int i = 0; i < n; i++) // Looping through the array length
        {   System.out.println("Sort Pass Number " + (i + 1));
            for(int j = 1; j < (n - i); j++)
            {
                System.out.println("Comparing " + array[j - 1] + " and " + array[j]);
                if(array[j - 1] > array[j])
                {
                    //swap elements
                    temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    System.out.println(array[j] + " is greater than " + array[j - 1]);
                    System.out.println("Swapping Elements: New Array After Swap");
                    printArray(array);
                }

            }
        }

    }

    static void printArray(int[] array){

        for(int i = 0; i < array.length; i++)
        {
            System.out.print(array[i] + " ");
        }
        System.out.println();

    }
}

Keluaran:

---Array BEFORE Bubble Sort---
860 8 200 9
Sort Pass Number 1
Comparing 860 and 8
860 is greater than 8
Swapping Elements: New Array After Swap
8 860 200 9
Comparing 860 and 200
860 is greater than 200
Swapping Elements: New Array After Swap
8 200 860 9
Comparing 860 and 9
860 is greater than 9
Swapping Elements: New Array After Swap
8 200 9 860
Sort Pass Number 2
Comparing 8 and 200
Comparing 200 and 9
200 is greater than 9
Swapping Elements: New Array After Swap
8 9 200 860
Sort Pass Number 3
Comparing 8 and 9
Sort Pass Number 4
---Array AFTER Bubble Sort---
8 9 200 860

Code penjelasan: The bubbleSort Metode ini menerima array berdasarkan referensi, sehingga pemanggil melihat hasil yang sudah diurutkan tanpa nilai kembalian apa pun. Variabel suhu mempertahankan satu nilai selama pertukaran tiga baris, itulah sebabnya algoritma hanya membutuhkan memori tambahan O(1). Ekspresi n –i Dalam kondisi loop bagian dalam, dijamin bahwa posisi yang sudah diurutkan di bagian ekor tidak akan pernah dikunjungi kembali.

Dioptimalkan Bubble Urutkan Program ke dalam Java

Program di atas selalu melakukan n-1 putaran, bahkan ketika array sudah terurut sejak awal. Menambahkan satu flag boolean memperbaiki inefisiensi tersebut. Jika satu putaran lengkap selesai tanpa satu pun pertukaran, array dijamin sudah terurut dan loop luar dapat berhenti segera.

package com.guru99;

public class OptimizedBubbleSort {

    public static void main(String[] args) {
        int arr[] = {5, 12, 33, 47, 58};
        bubbleSort(arr);
        System.out.println(java.util.Arrays.toString(arr));
    }

    static void bubbleSort(int[] array) {
        int n = array.length;
        int passes = 0;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 1; j < n - i; j++) {
                if (array[j - 1] > array[j]) {
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    swapped = true;
                }
            }
            passes++;
            // Early exit: the array is already sorted
            if (!swapped) {
                break;
            }
        }
        System.out.println("Passes executed: " + passes);
    }
}

Keluaran:

Passes executed: 1
[5, 12, 33, 47, 58]

Array input sudah diurutkan, sehingga versi yang dioptimalkan selesai setelah satu kali proses, bukan empat kali. Pada data yang hampir terurut, perubahan ini mengubah beban kerja kuadratik menjadi hampir linier, yang merupakan alasan utama. BubblFungsi e Sort masih muncul dalam kode nyata dari waktu ke waktu.

Kompleksitas Waktu dan Kompleksitas Ruang dari Bubble Urutkan

Kompleksitas menggambarkan bagaimana waktu eksekusi meningkat seiring dengan bertambahnya ukuran input. Untuk Bubble. Jumlah perbandingan pada versi yang belum dioptimalkan ditetapkan pada n(n-1)/2, yang menempatkannya secara pasti dalam kelas kuadratik.

Karena setiap pertukaran terjadi di dalam array asli dan hanya satu variabel sementara yang digunakan, Bubble Sort adalah algoritma in-place dengan ruang bantu O(1). Algoritma ini juga merupakan pengurutan stabil, artinya dua record yang memegang kunci yang sama mempertahankan urutan relatif aslinya setelah diurutkan.

Keuntungan dan Kerugian dari Bubble Urutkan

Memahami kedua sisi akan membantu Anda memutuskan kapan algoritma tersebut merupakan pilihan yang dapat diterima dan kapan algoritma tersebut harus diganti.

Kelebihan

• Kesederhanaan: Logika tersebut dapat diringkas dalam sekitar sepuluh baris, sehingga mudah untuk ditulis dengan benar dalam kondisi wawancara.
• Operasi di tempat: Tidak ada array tambahan yang dialokasikan, sehingga penggunaan memori tidak meningkat seiring dengan ukuran input.
• Stabilitas: Kunci yang sama mempertahankan urutan aslinya, yang penting saat mengurutkan catatan berdasarkan bidang sekunder.
• Deteksi keluar dini: Bendera "swapped" mengidentifikasi array yang sudah diurutkan dalam satu kali proses.

Kekurangan

• Pertumbuhan kuadratik: Mengurutkan 10,000 elemen membutuhkan hampir 50 juta perbandingan dalam skenario terburuk.
• Penulis yang berlebihan menulis: Algoritma ini melakukan lebih banyak pertukaran daripada Selection Sort, yang boros memori dengan operasi penulisan yang lambat.
• Skalabilitas yang buruk: Beban kerja produksi hampir selalu lebih menyukai Quicksort, Merge Sort, atau metode Arrays.sort bawaan.

Bubble Sort vs Pengurutan Lainnya Algorithms

Tabel di bawah ini membandingkannya BubblSelanjutnya, lakukan pengurutan dengan teknik pengurutan yang biasa dipelajari pemula, sehingga Anda dapat melihat dengan tepat di mana setiap teknik unggul.

BubblAlgoritma pengurutan e dan pengurutan sisipan memiliki kasus terbaik linier yang sama, tetapi pengurutan sisipan melakukan lebih sedikit pertukaran pada data yang sebagian sudah diurutkan. Pengurutan seleksi selalu melakukan tepat n-1 pertukaran, yang membuatnya padatracQuicksort atau Heap Sort efektif ketika operasi penulisan mahal, meskipun mengorbankan stabilitas. Untuk array yang lebih besar dari beberapa ratus elemen, Quicksort atau Heap Sort adalah pilihan yang tepat.

Setelah Anda terbiasa dengan pola penelusuran array yang digunakan di sini, struktur loop yang sama muncul dalam banyak latihan klasik seperti Deret Fibonacci dalam Java dan Java program palindrom. Revmelihat Java array dan lebih luas Java tutorial akan memperkuat dasar-dasar yang menjadi landasan algoritma ini.

Pertanyaan Umum Demo Slot