Perbedaan yang menonjol antara bubble sort dan insertion sort adalah bubble sort melakukan penyortiran dengan memeriksa unsur data tetangga dan menukarnya jika urutannya salah sementara insertion sort melakukan pengurutan dengan mentransfer satu unsur ke array yang diurutkan sebagian pada satu waktu.
Algoritma adalah urutan langkah-langkah untuk memecahkan suatu masalah . Penyortiran adalah operasi umum untuk dilakukan pada kumpulan data. Ada berbagai algoritma untuk mengurutkan kumpulan data. Dua di antaranya adalah bubble sort dan insertion sort. Selain itu, kedua algoritma ini dianggap sebagai algoritma pengurutan sederhana.
Topik bahasan kami tentang:
- Apa itu Bubble Sort – Definisi, Fungsionalitas 2. Apa itu Pengurutan Sisipan? – Definisi, Fungsionalitas 3. Perbedaan Antara Bubble Sort dan Insertion Sort – Perbandingan Perbedaan Kunci
Istilah Utama
Algoritma, Bubble Sort, Insertion Sort
Yang perlu anda ketahui tentang Bubble Sortir?
Bubble sort adalah algoritma pengurutan yang paling sederhana. Algoritma mengurutkan unsur dengan membandingkan pasangan yang berdekatan pada suatu waktu.
Perhatikan contoh berikut:
40 30 10 70 50 20 60
Dalam penyortiran gelembung, kita membandingkan unsur tetangga.
Pertama, kita anggap 40 dan 30. 30 kurang dari 40. Jadi, kita bisa menukar kedua angka tersebut.
30 40 10 70 50 20 60
Sekarang, kita dapat mempertimbangkan 40 dan 10. 10 kurang dari 40. Jadi, kita dapat menukar kedua angka tersebut.
30 10 40 70 50 20 60
Sekarang, kita dapat mempertimbangkan 40 dan 70. Karena 70 lebih besar dari 40, tidak perlu menukar angka.
Selanjutnya kita anggap 70 dan 50. 50 kurang dari 70. Jadi, kita bisa menukar kedua angka tersebut.
30 10 40 50 70 20 60
Kemudian, kita dapat mempertimbangkan 70 dan 20. Karena 20 kurang dari 70, kita dapat menukar kedua unsur tersebut.
30 10 40 50 20 70 60
Sekarang, kita dapat mempertimbangkan 70 dan 60. 60 kurang dari 70. Maka dari itu, kita harus menukar kedua angka tersebut.
30 10 40 50 20 60 70
Sekarang, Anda dapat melihat bahwa unsur terbesar dalam kumpulan data sekarang berada di akhir. Dengan kata lain, pada akhir lintasan pertama, unsur terbesar sudah diurutkan. Maka dari itu, lain kali, kita tidak perlu mempertimbangkan 70 karena sudah diurutkan. Kita hanya perlu memeriksa enam unsur lainnya.
Selain itu, kita harus melakukan perbandingan dua unsur sekaligus. Pertimbangkan 30 dan 10. 10 kurang dari 30. Jadi, kita menukar kedua angka itu.
10 30 40 50 20 60 70
Sekarang, kita menganggap 30 dan 40. 40 lebih besar dari 30. Tidak perlu menukar angka. Kemudian, kita dapat mempertimbangkan 40 dan 50. Karena 50 lebih besar dari 40, tidak perlu bertukar.
Sekarang, pertimbangkan 50 dan 20. 20 kurang dari 50. Jadi, kita menukar kedua angka itu.
10 30 40 20 50 60 70
Sekarang, pertimbangkan 50 dan 60. Tidak perlu bertukar. Pada akhir lintasan kedua, unsur terbesar kedua diurutkan. Dengan kata lain, 60 dan 70 sekarang diurutkan. Proses berlanjut sampai menyortir semua unsur.
Yang perlu anda ketahui tentang Pengurutan Sisipan?
Algoritma insertion sort mengurutkan dataset dengan mentransfer satu unsur pada satu waktu ke array yang diurutkan sebagian. Dengan demikian, algoritma pengurutan ini memiliki overhead yang rendah.
Perhatikan contoh berikut:
40 30 10 70 50 20 60
Kita menganggap 40 sebagai array yang diurutkan sebagian. Ketika kita mempertimbangkan 30, itu kurang dari 40. Jadi kita menukarnya. Kemudian, kita menganggap 30 dan 40 berada dalam array yang diurutkan sebagian.
30 40 10 70 50 20 60
Sekarang, kita anggap 10. 10 kurang dari 30. Jadi, kita tempatkan unsur-unsurnya seperti di bawah ini. 10, 30 dan 40 berada dalam array yang diurutkan sebagian.
10 30 40 70 50 20 60
Sekarang, kita pertimbangkan 70. Ini lebih besar dari 40, jadi tidak perlu ada gerakan apa pun. 10, 30, 40, 70 berada dalam array yang diurutkan sebagian.
Sekarang, pertimbangkan 50. Ini kurang dari 70 tetapi lebih besar dari 40. Kita dapat menempatkannya pada posisi yang benar. 10,30, 40, 50,70 sekarang berada dalam array yang diurutkan sebagian.
10 30 40 50 70 20 60
Sekarang, perhatikan 20. Lebih besar dari 10 tetapi kurang dari 20. Kita dapat menempatkannya pada posisi yang benar. 10,20,30,40,50, 70 berada dalam array yang diurutkan sebagian.
10 20 30 40 50 70 60
Pertimbangkan 60. Ini kurang dari 70 tetapi lebih besar dari 50. Kita dapat menempatkannya pada posisi yang benar.
10 20 30 40 50 60 70
Sekarang, kita dapat melihat bahwa semua unsur diurutkan. Di sini, jumlah swap dalam jenis penyisipan diminimalkan tetapi jumlah perbandingan masih tinggi.
Perbedaan Antara Bubble Sort dan Insertion Sort
Definisi
Bubble sort adalah algoritma pengurutan sederhana yang berulang kali melewati daftar, membandingkan pasangan yang berdekatan dan menukarnya jika urutannya salah. Pengurutan penyisipan, di sisi lain, adalah algoritme pengurutan sederhana yang membangun daftar pengurutan akhir dengan mentransfer satu unsur pada satu waktu. Jadi, inilah Perbedaan yang menonjol antara bubble sort dan insertion sort.
Kegunaan
Sementara bubble sort memeriksa unsur tetangga dan menukarnya sesuai dengan itu, insertion sort mentransfer unsur sekaligus ke array yang diurutkan sebagian.
Jumlah swap
Juga, jumlah swap merupakan perbedaan penting antara bubble sort dan insertion sort. Insertion sort memiliki jumlah swap yang lebih sedikit dibandingkan dengan bubble sort.
Kecepatan
Selain itu, insertion sort dua kali lebih cepat dari bubble sort.
Kompleksitas
Perbedaan lain antara bubble sort dan insertion sort adalah insertion sort lebih kompleks daripada bubble sort.
Kata terakhir
Bubble sort dan insertion sort cocok untuk menyortir kumpulan data kecil. Keduanya memiliki efisiensi yang lebih rendah jika dibandingkan dengan algoritma pengurutan lanjutan lainnya seperti quicksort dan merge sort . Perbedaan yang menonjol antara bubble sort dan insertion sort adalah bubble sort melakukan pengurutan dengan memeriksa unsur data tetangga dan menukarnya jika urutannya salah, sedangkan insertion sort melakukan pengurutan dengan mentransfer satu unsur ke array yang diurutkan sebagian pada satu waktu.
Sumber bacaan:
- “Urutan Gelembung.” Wikipedia, Wikimedia Foundation, 15 April 2019, Tersedia di sini . 2. “Urutan Penyisipan.” Wikipedia, Wikimedia Foundation, 3 Februari 2019, Tersedia di sini . 3.“Apa Itu Jenis Penyisipan? – Definisi dari Techopedia.” Techopedia.com, Tersedia di sini .
Sumber gambar:
1.1.”2816806″ (CC0) melalui Pixabay
