Perbedaan antara Sortir Gelembung dan Sortir Penyisipan

Bubble Sort Vs Insertion Sort

Bubble Sort adalah algoritma penyortiran yang beroperasi dengan melalui daftar untuk diurutkan berulang kali saat membandingkan pasangan elemen yang berdekatan. Jika sepasang elemen dalam urutan yang salah, mereka ditukar untuk menempatkannya dalam urutan yang benar. Traversal ini diulangi sampai tidak diperlukan pertukaran lebih lanjut. Penyisipan juga merupakan algoritma penyortiran, yang beroperasi dengan memasukkan elemen dalam daftar input ke posisi yang benar dalam daftar yang sudah diurutkan. Proses ini diterapkan berulang kali sampai daftar diurutkan.

Apa itu Bubble Sort?

Bubble Sort adalah algoritma penyortiran yang beroperasi dengan melalui daftar untuk diurutkan berulang kali saat membandingkan pasangan elemen yang berdekatan. Jika sepasang elemen dalam urutan yang salah, mereka ditukar untuk menempatkannya dalam urutan yang benar. Traversal ini diulangi sampai tidak diperlukan swap lebih lanjut (yang berarti daftar disortir). Karena elemen -elemen yang lebih kecil dalam daftar datang ke atas sebagai gelembung datang ke permukaan, itu diberi nama Bubble Sort. Bubble Sort adalah algoritma penyortiran yang sangat sederhana tetapi memiliki kompleksitas waktu kasus rata -rata O (N2) saat menyortir daftar dengan elemen N. Karena ini, jenis gelembung tidak cocok untuk menyortir daftar dengan sejumlah besar elemen. Tapi karena kesederhanaannya, jenis gelembung diajarkan selama perkenalan untuk algoritma.

Apa itu penyisipan?

Sort Penyisipan adalah algoritma penyortiran lain, yang beroperasi dengan memasukkan elemen dalam daftar input ke posisi yang benar dalam daftar (yang sudah diurutkan). Proses ini diterapkan berulang kali sampai daftar diurutkan. Dalam jenis penyisipan, penyortiran dilakukan di tempat. Oleh karena itu setelah iterasi algoritma, entri I+1 pertama dalam daftar akan diurutkan dan daftar lainnya 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. Sort Penyisipan memiliki kompleksitas waktu kasus rata -rata O (N2). Karena ini, jenis penyisipan juga tidak cocok untuk menyortir daftar besar.

Apa perbedaan antara Sortir Gelembung dan Sortir Penyisipan?

Meskipun kedua algoritma Sort Bubble Sort dan Insertion Sort memiliki kompleksitas waktu kasus rata -rata O (N2), Sort Bubble hampir sepanjang waktu diunggulkan oleh Sort Penyisipan. Ini karena jumlah swap yang dibutuhkan oleh dua algoritma (jenis gelembung membutuhkan lebih banyak swap). Tapi karena kesederhanaan semacam gelembung, ukuran kodenya sangat kecil. Juga ada varian dari jenis penyisipan yang disebut jenis shell, yang memiliki kompleksitas waktu O (n3/2), yang akan memungkinkannya digunakan secara praktis. Selain itu, jenis penyisipan sangat efisien untuk menyortir daftar "hampir disortir", bila dibandingkan dengan jenis gelembung.