Ringkasan
Penyortiran gelembung adalah algoritma penyortiran sederhana. Ini berulang kali mengunjungi urutan yang harus diurutkan, membandingkan dua elemen sekaligus, dan menukarnya jika mereka salah. Pekerjaan mengunjungi urutan diulangi sampai urutan telah diurutkan. Asal usul algoritma ini adalah karena semakin kecil elemen akan perlahan -lahan "melayang" ke awal urutan melalui pertukaran.
Sederhananya, itu adalah:
Penyortiran gelembung lebih dari sekadar karakter yang lebih besar tenggelam di belakang array (dapat dipahami seperti di bawah), dan karakter yang lebih kecil melayang di depan (di atas).
Diagram interpretasi intuitif:
melangkah
Bandingkan elemen yang berdekatan. Jika yang pertama lebih besar dari yang kedua, bertukar mereka dengan keduanya.
Lakukan pekerjaan yang sama untuk setiap pasangan elemen yang berdekatan, mulai dari pasangan pertama ke pasangan terakhir di akhir. Pada titik ini, elemen terakhir harus menjadi angka terbesar.
Ulangi langkah -langkah di atas untuk semua elemen kecuali yang terakhir.
Terus ulangi langkah -langkah di atas untuk lebih sedikit dan lebih sedikit elemen setiap kali sampai tidak ada pasangan angka yang perlu dibandingkan.
Contoh
Data mentah:
3 5 2 6 2
Babak pertama
Membandingkan 3 dan 5, 5 lebih besar dari 3, tidak ada pertukaran 3 5 2 6 2 Lanjutkan membandingkan 5 dan 2, 5 lebih besar dari 2, posisi pertukaran 3 2 5 6 2 Lanjutkan membandingkan 5 dan 6, 6 lebih besar dari 5, tidak ada pertukaran 3 2 5 6 2 Lanjutkan membandingkan 6 dan 2, lebih besar dari 2, posisi pertukaran 3 2 5 66 wastafel ke ujung, keduanya 2, 2, lebih besar dari 2).
Babak 2
Perbandingan 3 dan 2, 3 lebih besar dari 2, posisi pertukaran 2 3 5 2 6 Perbandingan 3 dan 5, 5 lebih besar dari 3, tidak ada pertukaran 2 3 5 2 6 Perbandingan 5 dan 2, 5 lebih besar dari 2, posisi pertukaran 2 3 2 5 6 Tidak perlu membandingkan 5 dan 6
Babak ketiga
Perbandingan 2 dan 3, 3 lebih besar dari 2, tidak perlu pertukaran 2 3 2 5 6 Perbandingan 3 dan 2, 3 lebih besar dari 2, tidak perlu membandingkan posisi pertukaran 2 2 3 5 6
Babak 4
Bandingkan 2 dan 2 tanpa pertukaran 2 2 3 5 6
Empat putaran akhir
2 2 3 5 6
Implementasi Kode (Java)
Paket com.coder4j.main.arithmetic.sorting; Public Class Bubble { / ** * Bubble Sort * * @param array * @return * / public static int [] sort (int [] array) {int temp; // Loop layer pertama menunjukkan jumlah putaran dibandingkan, seperti elemen panjang, dan jumlah putaran yang dibandingkan adalah panjang -1 (tidak perlu membandingkan dengan diri Anda) untuk (int i = 0; i <array.length - 1; i ++) {System.out.println ("Thread" + (i + 1) + "Roda start"); // Lapisan kedua loop, masing -masing dua perbandingan berdekatan berkurang sekali, dan berapa kali berkurang seiring dengan meningkatnya jumlah putaran. Setiap putaran menentukan yang terbesar, dan tidak perlu membandingkan yang terbesar untuk (int j = 0; j <array.length - 1 - i; j ++) {if (array [j+1] <array [j]) {temp = array [j]; array [j] = array [j + 1]; array [j + 1] = temp; } System.out.println ("th" + (i + 1) + "bulat," th " + (j + 1) +" bandingkan: "); untuk (int k: array) {System.out.print (k +" ");} System.out.println ();} System.out.println (" "); untuk (int (); System.outs.println ();Hasil output tes:
2 3 5 6 6 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 4 3 3 5 6 4 4 4 4 4 4 5 6 4 4 4 4 4 4 4 5 6 4 4 4 4 4 4 4 4 4 4 5 6 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 44 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 Hasil Akhir 2 2 3 5 6
Setelah pengujian, konsisten dengan hasil dalam contoh.