Pengantar Bubble Sort dan Seleksi Sort
Bubble sort merupakan algoritma pengurutan yang beroperasi dengan menelusuri daftar yang akan diurutkan berulang kali sambil membandingkan pasangan elemen yang berdekatan.
Jika sepasang elemen berada dalam urutan yang salah, mereka ditukar untuk menempatkannya dalam urutan yang benar.
Traversal ini diulangi sampai tidak diperlukan pertukaran lebih lanjut.
Pengurutan seleksi juga merupakan algoritma pengurutan, yang dimulai dengan menemukan elemen minimum dalam daftar dan menukarnya dengan elemen pertama.
Proses ini diulang untuk sisa daftar dengan menempatkan elemen yang ditukar secara berurutan.
Apa itu Bubble Sort?
Bubble sort adalah algoritma pengurutan yang beroperasi dengan menelusuri daftar yang akan diurutkan berulang kali sambil membandingkan pasangan elemen yang berdekatan.
Jika sepasang elemen berada dalam urutan yang salah, mereka ditukar untuk menempatkannya dalam urutan yang benar.
Traversal ini diulang sampai tidak diperlukan pertukaran lebih lanjut (yang berarti bahwa daftar diurutkan).
Karena elemen yang lebih kecil dalam daftar muncul ke atas saat gelembung muncul ke permukaan, ini diberi nama pengurutan gelembung.
Bubble sort adalah algoritme pengurutan yang sangat sederhana tetapi memiliki kompleksitas waktu kasus rata-rata O(n2) saat mengurutkan daftar dengan n elemen.
Oleh karena itu, pengurutan gelembung tidak cocok untuk menyortir daftar dengan banyak elemen.
Namun karena kesederhanaannya, bubble sort diajarkan selama pengenalan algoritma.
Apa itu Seleksi Seleksi?
Sortasi pilihan juga merupakan algoritma pengurutan lain yang dimulai dengan menemukan elemen minimum dalam daftar dan menukarnya dengan elemen pertama.
Kemudian elemen minimum ditemukan dari sisa daftar (dari elemen kedua hingga elemen terakhir dalam daftar) dan ditukar dengan elemen kedua.
Proses ini diulang untuk sisa daftar dengan menempatkan elemen yang ditukar secara berurutan.
Jadi dalam pengurutan seleksi, pada setiap langkah algoritme, daftar dibagi menjadi dua bagian di mana satu bagian berisi elemen yang diurutkan dan bagian lainnya berisi elemen yang tidak disortir.
Saat algoritme berjalan, daftar yang diurutkan tumbuh dari kiri ke kanan.
Pengurutan pilihan juga memiliki kompleksitas waktu kasus rata-rata O(n2).
Oleh karena itu juga tidak cocok untuk menyortir daftar besar.
Apa perbedaan antara Bubble Sort dan Selection Sort?
Meskipun algoritma pengurutan gelembung dan pengurutan pilihan memiliki kompleksitas waktu kasus rata-rata O(n2), pengurutan gelembung hampir selalu mengungguli pengurutan pilihan.
Ini karena jumlah swap yang dibutuhkan oleh kedua algoritma (jenis gelembung membutuhkan lebih banyak swap).
Namun karena kesederhanaan pengurutan gelembung, ukuran kodenya sangat kecil.
Stabilitas adalah perbedaan lain dalam kedua algoritma ini.
Algoritma penyortiran yang stabil, adalah algoritme penyortiran yang mempertahankan urutan catatan jika daftar berisi elemen dengan nilai yang sama.
Dalam pengertian itu, pengurutan seleksi bukanlah algoritma yang stabil sedangkan pengurutan gelembung adalah algoritma yang stabil.