Perbedaan Antara Bubble Sort dan Insertion Sort

Sortir Gelembung vs. Sortir Penyisipan

Bubble sort adalah algoritma pengurutan yang beroperasi dengan menelusuri daftar untuk diurutkan berulang kali sambil membandingkan pasangan elemen yang berdekatan. Jika sepasang elemen berada di urutan yang salah mereka ditukar untuk menempatkannya di urutan yang benar. Traversal ini diulangi sampai tidak ada swap lebih lanjut yang diperlukan. Sortasi penyisipan juga merupakan algoritma penyortiran, 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.

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 di urutan yang salah mereka ditukar untuk menempatkannya di urutan yang benar. Traversal ini diulangi sampai tidak ada swap lebih lanjut yang diperlukan (yang berarti bahwa daftar diurutkan). Karena elemen-elemen yang lebih kecil dalam daftar naik ke atas ketika gelembung muncul ke permukaan, diberi nama semacam gelembung. Bubble sort adalah algoritma penyortiran yang sangat sederhana tetapi memiliki kompleksitas waktu kasus rata-rata O (n2) ketika menyortir daftar dengan n elemen. Karena itu, sortir gelembung tidak cocok untuk menyortir daftar dengan sejumlah besar elemen. Namun karena kesederhanaannya, bubble sort diajarkan selama pengantar algoritma.

Apa itu Penyisipan Sortir?

Sortasi penyisipan adalah algoritma penyortiran 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 penyisipan sortir, penyortiran dilakukan di tempat. Oleh karena itu setelah iterasi algoritma, entri i + 1 pertama dalam daftar akan diurutkan dan sisa daftar tidak akan disortir. Pada setiap iterasi, elemen pertama di bagian yang tidak disortir dari daftar akan diambil dan dimasukkan ke tempat yang benar di bagian yang diurutkan dari daftar. Jenis penyisipan memiliki kompleksitas waktu kasus rata-rata O (n2). Karena itu, penyisipan juga tidak cocok untuk menyortir daftar besar.

Apa perbedaan antara Bubble Sort dan Insertion Sort?

Meskipun kedua jenis gelembung dan algoritma jenis penyisipan memiliki kompleksitas waktu kasus rata-rata O (n2), jenis gelembung hampir selalu melebihi kinerja jenis penyisipan. Ini disebabkan oleh jumlah swap yang dibutuhkan oleh kedua algoritma tersebut (jenis gelembung membutuhkan lebih banyak swap). Tetapi karena kesederhanaan semacam gelembung, ukuran kodenya sangat kecil. Juga ada varian jenis penyisipan yang disebut jenis shell, yang memiliki kompleksitas waktu O (n3 / 2), yang akan memungkinkannya untuk digunakan secara praktis. Selain itu, jenis penyisipan sangat efisien untuk menyortir daftar "hampir diurutkan", jika dibandingkan dengan jenis gelembung.