Sekarang kamu sudah tahu berbagai sorting algorithm. Mari bandingkan semuanya.
Tabel Perbandingan
| Algoritma | Best | Average | Worst | Space | Stabil? |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Ya |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Tidak |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Ya |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ya |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | Tidak |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Ya |
Kapan Pakai Yang Mana?
Data kecil (< 50 elemen): → Insertion Sort — overhead rendah, cepat untuk data kecil
Data hampir terurut: → Insertion Sort — best case O(n)
Butuh jaminan O(n log n): → Merge Sort — konsisten, stabil
Data besar, performa umum terbaik: → Quick Sort — paling cepat secara praktis
Data integer dengan range kecil: → Counting Sort — O(n), super cepat
Butuh stabilitas: → Merge Sort atau Insertion Sort
JavaScript Built-in Sort
// Array.sort() di V8 menggunakan TimSort
// TimSort = Merge Sort + Insertion Sort
const arr = [3, 1, 4, 1, 5, 9, 2, 6];
arr.sort((a, b) => a - b); // [1, 1, 2, 3, 4, 5, 6, 9]
Tip: Untuk kode production, gunakan built-in
.sort()kecuali ada kebutuhan spesifik. Tapi pahami cara kerja sorting agar bisa memilih pendekatan yang tepat.
🎭 Analogi sehari-hari: Pilih cara packing barang pindahan rumah. Banyak teknik:
- Bubble: keluar masuk dus ulang sampai rapi (lambat)
- Insertion: sisip satu-satu ke dus yang sudah rapi (cepat kalau sudah hampir rapi)
- Merge: packing per ruangan, gabungin (steady, butuh ruang ekstra)
- Quick: tentuin "barang patokan", kelompokin sebelum/sesudah, ulangi (cepat tapi bisa kacau)
- Counting: kalau barang tipe terbatas, langsung hitung per tipe (super cepat tapi terbatas tipe)
Pilih sesuai kondisi. Gak ada satu sort yang menang semua.
💡 Comparison sort theoretical lower bound = O(n log n). Buktinya: ada n! kemungkinan permutasi, butuh log₂(n!) ≈ n log n perbandingan minimum untuk membedakan. Itu kenapa Counting Sort bisa lebih cepat (gak comparison).
⚠️ Jebakan umum saat pilih sort:
- Premature optimization — pakai Counting Sort untuk 100 elemen padahal
.sort()sudah cukup - Lupa stability — jika urutan asli matter (sort stable transactions), Quick Sort bisa rusak
- Ngotot reimplementasi — hampir selalu
.sort()builtin lebih cepat dari yang kamu tulis (TimSort/IntroSort sudah dioptimasi heavily) - Lupa konstanta — algoritma O(n log n) tertentu konstanta-nya 10x dari yang lain
🎯 Decision tree pilih sort:
- Data kecil (<50)? → Insertion atau builtin
- Data sudah hampir sorted? → Insertion
- Data integer range kecil? → Counting / Radix
- Butuh stable? → Merge / TimSort
- Memory tight? → Heap
- Data besar acak? → Quick atau builtin (TimSort)
- 99% kasus: pakai
.sort()builtin
🧪 Tebakan cepat: Sort 1jt transaksi by tanggal lalu by jumlah. Pakai Quick Sort? Bisa salah karena tidak stable — transaksi dengan tanggal sama bisa keluar urutan jumlah. Pakai Merge Sort atau TimSort builtin (stable).
TL;DR: Sort algorithm bukan one-size-fits-all. Pilih berdasar: ukuran data, sifat data, stability, memory. 99% praktiknya pakai .sort() builtin (TimSort). Hafalin trade-off untuk interview & corner cases.
