Perbedaan antara jenis gelembung dan jenis seleksi

Bubble Sort vs Sort Pilihan

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. Sort Pilihan juga merupakan algoritma penyortiran, yang dimulai dengan menemukan elemen minimum dalam daftar dan menukarnya dengan elemen pertama. Proses ini diulangi untuk sisa daftar dengan menempatkan elemen bertukar secara berurutan.

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 jenis seleksi?

Sortian Seleksi juga merupakan algoritma penyortiran lain yang dimulai dengan menemukan elemen minimum dalam daftar dan menukarnya dengan elemen pertama. Maka elemen minimum ditemukan dari sisa daftar (dari elemen kedua hingga elemen terakhir dalam daftar) dan ditukar dengan elemen kedua. Proses ini diulangi untuk sisa daftar dengan menempatkan elemen bertukar secara berurutan. Jadi dalam jenis seleksi, pada setiap langkah algoritma, daftar dibagi menjadi dua bagian di mana satu bagian berisi elemen yang diurutkan dan bagian lainnya berisi elemen yang tidak disortir. Saat algoritma berlangsung, 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 jenis gelembung dan jenis seleksi?

Meskipun baik algoritma Sortir Bubble dan Algoritma Seleksi memiliki kompleksitas waktu kasus rata -rata O (N2), Sort Bubble hampir sepanjang waktu diunggulkan oleh jenis seleksi. Ini karena jumlah swap yang dibutuhkan oleh dua algoritma (jenis gelembung membutuhkan lebih banyak swap). Tapi karena kesederhanaan semacam gelembung, ukuran kodenya sangat kecil. Stabilitas adalah perbedaan lain dalam dua algoritma ini. Algoritma penyortiran yang stabil, adalah algoritma penyortiran yang mempertahankan urutan catatan jika daftar berisi elemen dengan nilai yang sama. Dalam hal itu, jenis seleksi bukanlah algoritma yang stabil sedangkan jenis gelembung adalah algoritma yang stabil.