Isih Buih lwn Isih Sisipan
Bubble sort ialah algoritma pengisihan yang beroperasi dengan melalui senarai untuk diisih berulang kali sambil membandingkan pasangan elemen yang bersebelahan. Jika sepasang elemen berada dalam susunan yang salah, ia ditukar untuk meletakkannya dalam susunan yang betul. Traversal ini diulang sehingga tiada pertukaran selanjutnya diperlukan. Isihan sisipan juga merupakan algoritma pengisihan, yang beroperasi dengan memasukkan elemen dalam senarai input ke kedudukan yang betul dalam senarai yang telah diisih. Proses ini digunakan berulang kali sehingga senarai diisih.
Apakah Isih Buih?
Bubble sort ialah algoritma pengisihan yang beroperasi dengan melalui senarai untuk diisih berulang kali sambil membandingkan pasangan elemen yang bersebelahan. Jika sepasang elemen berada dalam susunan yang salah, ia ditukar untuk meletakkannya dalam susunan yang betul. Traversal ini diulang sehingga tiada pertukaran lanjut diperlukan (yang bermaksud senarai itu diisih). Memandangkan unsur-unsur yang lebih kecil dalam senarai muncul di bahagian atas apabila gelembung muncul ke permukaan, ia diberi nama jenis gelembung. Isih gelembung ialah algoritma pengisihan yang sangat mudah tetapi ia mempunyai purata kerumitan masa kes O(n2) apabila mengisih senarai dengan n elemen. Disebabkan ini, isihan gelembung tidak sesuai untuk mengisih senarai dengan bilangan elemen yang banyak. Tetapi kerana kesederhanaannya, isihan gelembung diajar semasa pengenalan kepada algoritma.
Apakah Isih Sisipan?
Isihan sisipan ialah algoritma pengisihan lain, yang beroperasi dengan memasukkan elemen dalam senarai input ke kedudukan yang betul dalam senarai (yang telah diisih). Proses ini digunakan berulang kali sehingga senarai diisih. Dalam isihan sisipan, pengisihan dijalankan di tempat. Oleh itu selepas lelaran ke-3 algoritma, entri i+1 pertama dalam senarai akan diisih dan senarai yang lain akan dinyahsusun. Pada setiap lelaran, elemen pertama dalam bahagian senarai yang tidak diisih akan diambil dan dimasukkan ke tempat yang betul dalam bahagian yang diisih dalam senarai. Isihan sisipan mempunyai purata kerumitan masa kes O(n2). Disebabkan ini, isihan sisipan juga tidak sesuai untuk mengisih senarai besar.
Apakah perbezaan antara Isih Buih dan Isih Sisipan?
Walaupun kedua-dua algoritma isihan gelembung dan isihan sisipan mempunyai purata kerumitan masa kes O(n2), isihan gelembung hampir sepanjang masa mengatasi prestasi isihan sisipan. Ini disebabkan oleh bilangan swap yang diperlukan oleh kedua-dua algoritma (isihan gelembung memerlukan lebih banyak swap). Tetapi disebabkan kesederhanaan jenis gelembung, saiz kodnya sangat kecil. Terdapat juga varian jenis sisipan yang dipanggil jenis shell, yang mempunyai kerumitan masa O(n3/2), yang membolehkan ia digunakan secara praktikal. Tambahan pula, isihan sisipan sangat cekap untuk mengisih senarai "hampir diisih", jika dibandingkan dengan isihan gelembung.
