Urutan Gelembung vs Sortir Seleksi
Bubble sort adalah algoritma pengurutan yang beroperasi dengan menelusuri daftar untuk 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 ada swap lebih lanjut yang diperlukan. Sortir 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 untuk 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 ada swap lebih lanjut diperlukan (yang berarti bahwa daftar diurutkan). Karena elemen yang lebih kecil dalam daftar muncul ke atas saat gelembung muncul ke permukaan, maka diberi nama bubble sort. Bubble sort adalah algoritma pengurutan yang sangat sederhana tetapi memiliki kompleksitas waktu kasus rata-rata O(n2) ketika mengurutkan daftar dengan n elemen. Karena itu, bubble sort tidak cocok untuk mengurutkan daftar dengan banyak elemen. Namun karena kesederhanaannya, bubble sort diajarkan selama pengenalan algoritma.
Apa itu Pengurutan Seleksi?
Selection sort 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 pemilihan, pada setiap langkah algoritme, daftar dibagi menjadi dua bagian di mana satu bagian berisi elemen yang diurutkan dan bagian lainnya berisi elemen yang tidak diurutkan. Saat algoritma berjalan, daftar yang diurutkan tumbuh dari kiri ke kanan. Jenis seleksi 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 bubble sort dan selection sort memiliki kompleksitas waktu kasus rata-rata O(n2), bubble sort hampir selalu mengungguli seleksi. Hal ini dikarenakan banyaknya swap yang dibutuhkan oleh kedua algoritma tersebut (bubble sort membutuhkan lebih banyak swap). Tetapi karena kesederhanaan bubble sort, ukuran kodenya sangat kecil. Stabilitas adalah perbedaan lain dalam kedua algoritma ini. Algoritme pengurutan stabil, adalah algoritme pengurutan yang mempertahankan urutan catatan jika daftar berisi elemen dengan nilai yang sama. Dalam hal ini, selection sort bukanlah algoritma yang stabil sedangkan bubble sort adalah algoritma yang stabil.
