Bubble sort, insertion sort, dan selection sort sama-sama algoritma pengurutan sederhana yang diajarkan di awal belajar algoritma. Ketiganya mudah ditulis, tetapi punya perilaku berbeda saat data membesar atau sudah hampir terurut. Perbandingan metode pengurutan data bubble insertion selection membantu kamu memilih yang paling sesuai untuk kasus nyata, bukan sekadar menghafal kode.
Cara Kerja Singkat Masing-Masing Algoritma
Bubble Sort: Tukar Berulang
Bubble sort membandingkan dua elemen bersebelahan dan menukarnya jika urutannya salah. Proses ini diulang dari awal hingga tidak ada lagi pertukaran. Setiap putaran memastikan elemen terbesar bergerak ke posisi akhir, seperti gelembung yang naik ke permukaan.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arrInsertion Sort: Sisipkan ke Posisi Tepat
Insertion sort membangun array terurut satu per satu. Ia mengambil elemen berikutnya dan menyisipkannya ke posisi yang benar di antara elemen yang sudah terurut, mirip cara orang mengurutkan kartu di tangan.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arrSelection Sort: Pilih Terkecil, Tukar ke Depan
Selection sort mencari elemen terkecil di sisa array yang belum terurut, lalu menukarnya dengan elemen di posisi paling depan dari bagian yang belum terurut. Proses ini diulang hingga seluruh array terurut.
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arrKetiga algoritma ini sering muncul sebagai langkah awal sebelum mempelajari metode yang lebih efisien. Jika kamu baru mulai, 7 Algoritma Sorting yang Wajib Dikuasai Pemula bisa menjadi lanjutan setelah memahami dasar ini.
Perbandingan Efisiensi: Kompleksitas Waktu dan Ruang
Secara umum, ketiganya memiliki kompleksitas waktu O(n^2) pada kasus rata-rata dan terburuk. Ada perbedaan pada kasus terbaik dan penggunaan memori.
| Algoritma | Kasus Terbaik | Kasus Rata-rata | Kasus Terburuk | Ruang | Stabil? |
|---|---|---|---|---|---|
| Bubble Sort | O(n) (dengan optimasi) | O(n^2) | O(n^2) | O(1) | Ya |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | Ya |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | Tidak |
Insertion sort unggul saat data hampir terurut karena hanya perlu sedikit pergeseran. Bubble sort bisa mencapai O(n) jika dioptimasi dengan penanda pertukaran, tetapi jarang lebih cepat dari insertion sort dalam praktik. Selection sort selalu melakukan O(n^2) perbandingan, tetapi jumlah pertukaran paling sedikit (maksimal n-1), sehingga cocok ketika biaya menulis data mahal.
Kapan Sebaiknya Memakai Masing-Masing?
- Insertion sort: dataset kecil (di bawah 50 elemen) atau data yang sudah hampir terurut. Banyak implementasi library menggunakan insertion sort untuk partisi kecil dalam algoritma hybrid seperti Timsort.
- Selection sort: ketika jumlah pertukaran perlu diminimalkan, misalnya pada media penyimpanan dengan siklus tulis terbatas. Karena tidak stabil, hati-hati jika urutan relatif elemen sama penting.
- Bubble sort: terutama untuk tujuan edukasi. Di produksi, algoritma ini jarang dipakai karena kurang efisien dibanding yang lain.
Untuk data berukuran besar, algoritma O(n log n) seperti merge sort atau quick sort lebih tepat. Memahami ketiga algoritma dasar ini membantumu mengenali pola dan trade-off yang muncul di algoritma lanjutan.
Contoh Penerapan dalam Kasus Sederhana
Misalkan kamu memiliki array [5, 2, 9, 1, 7] dan ingin mengurutkannya secara ascending. Mari lihat langkah yang diambil masing-masing algoritma.
Bubble sort akan membandingkan 5 dan 2, menukar menjadi [2,5,9,1,7], lalu membandingkan 5 dan 9 (tidak tukar), 9 dan 1 (tukar menjadi [2,5,1,9,7]), 9 dan 7 (tukar menjadi [2,5,1,7,9]). Putaran pertama selesai dengan 9 di posisi akhir. Proses berlanjut hingga terurut.
Insertion sort mulai dengan elemen kedua (2). Karena 2 < 5, sisipkan sebelum 5 menghasilkan [2,5,9,1,7]. Elemen ketiga (9) sudah di posisi benar. Elemen keempat (1) disisipkan ke depan menjadi [1,2,5,9,7]. Terakhir, 7 disisipkan sebelum 9 menjadi [1,2,5,7,9].
Selection sort mencari nilai terkecil di seluruh array (1) dan menukarnya dengan elemen pertama (5) menghasilkan [1,2,9,5,7]. Lalu cari terkecil di sisa [2,9,5,7] yaitu 2, sudah di posisi. Lanjut cari terkecil di [9,5,7] yaitu 5, tukar dengan 9 menjadi [1,2,5,9,7]. Terakhir tukar 9 dan 7 menjadi [1,2,5,7,9].
Selection sort melakukan lebih sedikit pertukaran (tiga kali) dibanding bubble sort (empat kali) pada contoh ini, tetapi jumlah perbandingan tetap sama.
Kesalahan Umum Saat Menerapkan
Beberapa jebakan sering muncul ketika menulis ketiga algoritma ini. Pada bubble sort, lupa memberi batas inner loop (n-i-1) menyebabkan pemborosan perbandingan. Pada insertion sort, kesalahan indeks saat menggeser elemen bisa membuat data hilang. Pada selection sort, tertukar antara indeks minimum dan nilai minimum.
Selalu uji dengan array kosong, satu elemen, dan data duplikat. Untuk debugging, kamu bisa memanfaatkan console seperti dijelaskan dalam tips jQuery untuk pemula: debug kode dengan console, prinsipnya serupa: cetak keadaan array setiap iterasi untuk melihat pola.
Jika ingin memperdalam algoritma pengurutan lain, lihat perbandingan struktur data untuk belajar algoritma karena pemilihan struktur data memengaruhi efisiensi pengurutan.
Ringkasan
Bubble sort, insertion sort, dan selection sort memiliki kompleksitas waktu rata-rata O(n^2), tetapi karakter berbeda: insertion sort unggul untuk data hampir terurut, selection sort minim pertukaran, dan bubble sort lebih cocok untuk pembelajaran. Untuk dataset besar, pertimbangkan algoritma O(n log n). Pahami trade-off-nya agar bisa memilih yang tepat sesuai kebutuhan.
Pertanyaan yang Sering Diajukan
Apakah bubble sort masih relevan untuk dipelajari?
Ya, untuk memahami konsep dasar pertukaran dan loop bersarang. Di dunia kerja, algoritma ini jarang dipakai karena kurang efisien.
Mengapa insertion sort lebih cepat pada data yang hampir terurut?
Karena insertion sort hanya perlu menggeser elemen sedikit ketika data sudah hampir rapi, sehingga mendekati O(n). Sementara bubble sort dan selection sort tetap melakukan banyak perbandingan.
Algoritma mana yang paling stabil?
Bubble sort dan insertion sort bersifat stabil (mempertahankan urutan relatif elemen sama), sedangkan selection sort tidak stabil. Stabilitas penting jika kamu mengurutkan berdasarkan beberapa kriteria secara bertahap.