Pengurutan Gelembung vs Pengurutan Sisipan
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. Pengurutan penyisipan juga merupakan algoritme pengurutan, yang beroperasi dengan menyisipkan elemen dalam daftar input ke posisi yang benar dalam daftar yang sudah diurutkan. Proses ini dilakukan berulang kali hingga daftar diurutkan.
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 Insertion Sortir?
Insertion sort adalah algoritma pengurutan lain, yang beroperasi dengan menyisipkan elemen dalam daftar input ke posisi yang benar dalam daftar (yang sudah diurutkan). Proses ini diterapkan berulang kali hingga daftar diurutkan. Dalam insertion sort, sortasi dilakukan di tempat. Oleh karena itu setelah iterasi ke-i dari algoritma, entri i+1 pertama dalam daftar akan diurutkan dan sisa daftar tidak akan disortir. Pada setiap iterasi, elemen pertama di bagian daftar yang tidak diurutkan akan diambil dan dimasukkan ke tempat yang benar di bagian daftar yang diurutkan. Jenis penyisipan memiliki kompleksitas waktu kasus rata-rata O(n2). Oleh karena itu, insertion sort juga tidak cocok untuk menyortir 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. 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. Juga ada varian dari insertion sort yang disebut shell sort, yang memiliki kompleksitas waktu O(n3/2), yang memungkinkannya untuk digunakan secara praktis. Selain itu, insertion sort sangat efisien untuk menyortir daftar yang “hampir diurutkan”, jika dibandingkan dengan bubble sort.
