Pengantar Bubble Sort dan Insertion 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.
Jenis penyisipan juga merupakan algoritma pengurutan, yang beroperasi dengan memasukkan elemen dalam daftar input ke posisi yang benar dalam daftar yang sudah diurutkan.
Proses ini diterapkan berulang kali hingga daftar diurutkan.
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 Insertion Sort?
Jenis penyisipan adalah algoritma pengurutan lain, yang beroperasi dengan memasukkan elemen dalam daftar input ke posisi yang benar dalam daftar (yang sudah diurutkan).
Proses ini diterapkan berulang kali hingga daftar diurutkan.
Dalam pengurutan penyisipan, pengurutan dilakukan di tempat.
Oleh karena itu, setelah iterasi ke-i dari algoritme, entri i+1 pertama dalam daftar akan diurutkan dan daftar lainnya tidak akan diurutkan.
Pada setiap iterasi, elemen pertama di bagian yang tidak diurutkan dari daftar akan diambil dan dimasukkan ke tempat yang benar di bagian yang diurutkan dari daftar.
Urutan penyisipan memiliki kompleksitas waktu kasus rata-rata O(n2).
Oleh karena itu, sortir penyisipan juga tidak cocok untuk mengurutkan daftar besar.
Apa perbedaan antara Bubble Sort dan Insertion Sort?
Meskipun algoritma bubble sort dan insertion sort memiliki kompleksitas waktu kasus rata-rata O(n2), bubble sort hampir selalu mengungguli insertion sort.
Ini karena jumlah swap yang dibutuhkan oleh kedua algoritma (jenis gelembung membutuhkan lebih banyak swap).
Namun karena kesederhanaan pengurutan gelembung, ukuran kodenya sangat kecil.
Juga ada varian insertion sort yang disebut shell sort, yang memiliki kompleksitas waktu O(n3/2), yang memungkinkannya digunakan secara praktis.
Selain itu, pengurutan penyisipan sangat efisien untuk mengurutkan daftar “hampir terurut”, jika dibandingkan dengan pengurutan gelembung.