Algoritma Pengurutan — Perbandingan Bubble Sort, Merge Sort, dan Quick Sort

Algoritma pengurutan menyusun ulang item yang sama ke dalam urutan tertentu, misalnya dari yang terkecil ke yang terbesar. Jika ingin jawaban singkatnya dulu, bubble sort itu sederhana tetapi biasanya terlalu lambat untuk daftar besar, merge sort memberi performa $O(n \log n)$ yang andal, dan quick sort sering cepat dalam praktik ketika partisinya tetap cukup seimbang.

Pertanyaan yang tepat bukan "algoritma pengurutan mana yang terbaik?" melainkan "terbaik dalam kondisi apa?" Bubble sort mengajarkan pertukaran lokal, merge sort menunjukkan divide-and-conquer dengan jelas, dan quick sort menunjukkan mengapa kecepatan rata-rata bisa sangat baik meskipun tanpa jaminan kasus terburuk.

Apa yang Dilakukan Algoritma Pengurutan

Diberikan sebuah daftar seperti $[5, 1, 4, 2]$, algoritma harus mengembalikan nilai yang sama dalam urutan yang benar:

$$[1, 2, 4, 5]$$

Kedengarannya sederhana, tetapi algoritma yang berbeda mencapai hasil itu dengan cara yang sangat berbeda. Perbedaan utamanya adalah:

• bagaimana item dipindahkan
• berapa banyak perbandingan atau pertukaran yang biasanya digunakan
• berapa banyak memori tambahan yang dibutuhkan
• seberapa sensitif algoritma terhadap pola input yang buruk

Bubble Sort: Pertukaran Berulang Antar-Tetangga

Bubble sort berjalan menyusuri daftar dan menukar item yang bersebelahan jika urutannya salah. Setelah satu lintasan penuh, item terbesar yang belum terurut akan "mengambang" ke bagian akhir.

Pada $[5, 1, 4, 2]$, lintasan pertama terlihat seperti ini:

$$[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]$$

Lalu proses ini diulang pada bagian yang masih belum terurut sampai tidak ada pertukaran lagi yang diperlukan.

Bubble sort terutama berguna untuk belajar. Secara umum, kompleksitas waktunya adalah $O(n^2)$, sehingga jumlah perbandingan bertambah cepat saat daftar makin besar. Untuk contoh kecil di kelas, itu tidak masalah. Untuk pekerjaan pengurutan yang serius, biasanya ini bukan pilihan yang tepat.

Merge Sort: Bagi, Urutkan, Lalu Gabungkan

Merge sort menggunakan ide divide-and-conquer. Algoritma ini membagi daftar menjadi bagian-bagian yang lebih kecil, mengurutkan bagian-bagian itu, lalu menggabungkan kembali potongan yang sudah terurut.

Untuk $[5, 1, 4, 2]$, salah satu cara melihatnya adalah:

$$[5, 1, 4, 2] \to [5, 1] + [4, 2]$$

Urutkan setiap setengah bagian:

$$[5, 1] \to [1, 5], \qquad [4, 2] \to [2, 4]$$

Lalu gabungkan dua bagian yang sudah terurut:

$$[1, 5] + [2, 4] \to [1, 2, 4, 5]$$

Kekuatan utama merge sort adalah keterprediksiannya. Waktu jalannya adalah $O(n \log n)$ dalam analisis biasa, bukan hanya rata-rata. Biaya utamanya adalah memori: implementasi umum berbasis array menggunakan ruang tambahan saat proses penggabungan.

Quick Sort: Partisi di Sekitar Pivot

Quick sort juga menggunakan divide-and-conquer, tetapi dengan cara yang berbeda. Algoritma ini memilih sebuah pivot, menempatkan item yang lebih kecil di satu sisi dan item yang lebih besar di sisi lain, lalu mengurutkan kedua sisi itu secara rekursif.

Dengan pivot $4$ pada $[5, 1, 4, 2]$, salah satu partisi yang mungkin adalah:

$$[1, 2] \;|\; 4 \;|\; [5]$$

Sekarang bagian kiri dan kanan menjadi jauh lebih kecil, sehingga proses pengurutan selesai dengan cepat.

Quick sort sering cepat dalam praktik karena banyak implementasi melakukan partisi secara in-place dan memperkecil masalah dengan cepat ketika pivot membagi daftar dengan cukup baik. Tetapi kondisi itu penting. Jika pemilihan pivot berulang kali buruk, misalnya terus menghasilkan satu sisi yang sangat kecil dan satu sisi yang hampir penuh, maka kasus terburuknya menjadi $O(n^2)$.

Bubble Sort vs Merge Sort vs Quick Sort

Algoritma	Ide inti	Waktu tipikal	Waktu kasus terburuk	Memori tambahan
Bubble sort	Pertukaran berulang antar-item bersebelahan	$O(n^2)$	$O(n^2)$	Rendah
Merge sort	Bagi, urutkan tiap setengah, lalu gabungkan	$O(n \log n)$	$O(n \log n)$	Lebih tinggi pada implementasi array yang umum
Quick sort	Partisi di sekitar pivot	Sering $O(n \log n)$	$O(n^2)$	Sering lebih rendah daripada merge sort

Jika ingin satu kesimpulan praktis, ini intinya: bubble sort adalah algoritma untuk pembelajaran, merge sort adalah pilihan yang stabil dan dapat diprediksi, dan quick sort sering menjadi pilihan cepat dalam praktik ketika implementasinya menangani pivot dengan baik.

Satu Contoh yang Dikerjakan pada Daftar yang Sama

Gunakan daftar yang sama:

$$[5, 1, 4, 2]$$

Bubble sort terus memperbaiki kesalahan lokal. Algoritma ini tidak "melihat" seluruh struktur, jadi mungkin membutuhkan banyak lintasan.

Merge sort terlebih dahulu memecah masalah menjadi bagian-bagian kecil yang sudah terurut, lalu menggabungkannya. Struktur inilah yang membuat performanya tetap andal saat daftar bertambah besar.

Quick sort mencoba membuat satu pemisahan yang kuat sejak awal. Jika pemisahannya cukup seimbang, sisa pekerjaannya cepat menyusut.

Inilah sebabnya siswa sering lebih mudah mengingat angka kompleksitas setelah melihat satu daftar bergerak melalui setiap metode. Angka-angka itu bukan sekadar label acak. Angka-angka itu mencerminkan bagaimana algoritma mengurangi ketidakteraturan.

Kesalahan Umum Saat Membandingkan Algoritma Pengurutan

Menganggap Quick Sort Selalu Lebih Cepat

Quick sort sering cepat dalam praktik, tetapi tidak dijamin paling cepat dalam setiap kasus. Perilaku pivot yang buruk bisa sangat merugikannya.

Menganggap Semua Algoritma $O(n \log n)$ Itu Sama

Merge sort dan quick sort bisa memiliki laju pertumbuhan rata-rata yang sama tanpa berperilaku sama dalam penggunaan memori, jaminan kasus terburuk, atau detail implementasi.

Menggunakan Bubble Sort Karena Mudah Ditulis

Mudah ditulis tidak sama dengan cocok digunakan. Untuk demo kecil, bubble sort tidak masalah. Untuk input nyata yang lebih besar, biasanya algoritma ini melakukan pekerjaan yang tidak perlu.

Melupakan Model Input

Perbandingan ini biasanya mengasumsikan pengurutan berbasis perbandingan pada input umum. Jika datanya memiliki struktur khusus, algoritma pengurutan non-perbandingan seperti counting sort bisa mengubah keputusan sepenuhnya.

Kapan Setiap Algoritma Pengurutan Digunakan

Bubble sort sebagian besar digunakan untuk pembelajaran, penelusuran langkah demi langkah, dan contoh yang sangat kecil ketika kejelasan lebih penting daripada performa.

Merge sort digunakan ketika perilaku $O(n \log n)$ yang konsisten itu penting dan memori tambahan masih dapat diterima. Algoritma ini juga cocok secara alami untuk linked list dan untuk situasi ketika stable sorting penting, tergantung implementasinya.

Quick sort digunakan ketika kecepatan praktis itu penting dan implementasinya memiliki strategi pivot yang baik atau perlindungan cadangan. Banyak strategi pengurutan di pustaka standar menggunakan ide quick sort bersama pengaman, bukan versi buku teks yang naif.

Cara Cepat Mengingat Perbedaannya

Ingat berdasarkan gerakannya:

• bubble sort memperbaiki tetangga
• merge sort membangun bagian-bagian terurut
• quick sort membagi di sekitar pivot

Gambaran mental itu lebih berguna daripada menghafal tiga nama dan tiga rumus.

Coba Versi Anda Sendiri

Ambil daftar $[7, 3, 6, 1]$ dan telusuri satu lintasan bubble sort, satu siklus bagi-dan-gabung dari merge sort, dan satu partisi pivot untuk quick sort. Jika Anda bisa menjelaskan mengapa daftar berubah secara berbeda pada tiap kasus, berarti konsepnya sudah benar-benar dipahami.