Sorting — dari bubble sampai quick sort

Lima algoritma pengurutan yang paling sering keluar di ujian, lengkap dengan animasi langkah demi langkah.

Sorting mengubah urutan elemen menjadi menaik (ascending) atau menurun (descending). Hampir semua algoritma lain memanfaatkannya: binary search butuh data terurut, mencari duplikat jadi mudah setelah diurutkan, dan seterusnya.

Coba putar animasinya. Warna kuning = sedang dibandingkan, merah = ditukar, hijau = sudah di posisi akhir.

Algoritma O(n²): sederhana tapi lambat

Bubble sort membandingkan pasangan bersebelahan dan menukarnya bila salah urutan. Setelah putaran ke- $i$ , elemen terbesar ke- $i$ “menggelembung” ke ujung kanan. Optimasi penting: jika satu putaran tidak ada pertukaran, berhenti.

Selection sort mencari minimum dari bagian yang belum urut, lalu menaruhnya di depan. Jumlah perbandingannya selalu $\frac{n(n-1)}{2}$ , tapi jumlah pertukarannya paling banyak $n-1$ . Berguna kalau menulis ke memori itu mahal.

Insertion sort seperti mengurutkan kartu di tangan: ambil satu kartu, sisipkan ke posisi yang tepat di bagian kiri yang sudah urut. Pada data yang hampir urut, insertion sort mendekati $O(n)$ . Coba tombol “Hampir urut” di atas.

Algoritma O(n log n): divide and conquer

Merge sort membagi array jadi dua, mengurutkan masing-masing secara rekursif, lalu menggabungkan dua bagian terurut. Pembagian menghasilkan $\log_2 n$ level, dan tiap level butuh $O(n)$ untuk merge:

T(n) = 2\,T(n/2) + O(n) \;\Rightarrow\; T(n) = O(n \log n)

Quick sort memilih pivot, lalu mempartisi: elemen lebih kecil ke kiri, lebih besar ke kanan. Pivot langsung berada di posisi akhirnya. Rata-rata $O(n \log n)$ , tapi jika pivot selalu elemen terkecil/terbesar (misalnya data sudah urut dan pivot = elemen terakhir), kompleksitasnya jatuh ke $O(n^2)$ .

Ringkasan

Algoritma	Terbaik	Rata-rata	Terburuk	Memori	Stabil?
Bubble	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	ya
Selection	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	tidak
Insertion	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	ya
Merge	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	ya
Quick	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	tidak

Latihan: Urutkan Array (merge sort), Merge Two Sorted Arrays.