Kamu sudah kenal tujuh cara mengurutkan, dari bubble sort sampai counting sort. Pelajaran ini menaruh semuanya berdampingan supaya kamu bisa memilih: mana yang cepat untuk datamu, mana yang hemat memori, dan mana yang menjaga urutan data yang nilainya sama. Gak ada satu sort yang menang di semua data.
🧪 Tebakan cepat:
arr.sort()di Chrome dan Node.js memakai algoritma apa: quick sort, merge sort, atau campuran dua algoritma? Tebak dulu, jawabannya ada di bagian "Di JavaScript, pakaiarr.sort()".
Satu data, beda pemenang
Di Lab, empat sort berlomba mengurutkan 7 angka yang sama, dan yang paling sedikit membandingkan menang. Banyaknya perbandingan:
| Data | Bubble | Insertion | Merge | Quick |
|---|---|---|---|---|
Acak [38, 27, 43, 3, 9, 82, 10] |
21 | 15 | 13 | 11 |
Hampir terurut [3, 9, 10, 27, 38, 82, 43] |
21 | 7 | 9 | 16 |
Terbalik [82, 43, 38, 27, 10, 9, 3] |
21 | 21 | 11 | 21 |
- Data acak: quick sort menang.
- Hampir terurut: insertion sort menang jauh, karena hampir tiap angka cukup dicek sekali dengan tetangga kirinya. Quick sort malah kesulitan, karena pivot terakhirnya hampir selalu angka terbesar.
- Terbalik: merge sort menang. Tiga lainnya kena kasus terburuk, 21 = 7 × 6 / 2 perbandingan.
Tiap pembalap dapat salinan data yang sama, supaya adil:
const data = [38, 27, 43, 3, 9, 82, 10];
const urut = [...data].sort((a, b) => a - b);
console.log(urut); // [3, 9, 10, 27, 38, 43, 82]
console.log(data); // [38, 27, 43, 3, 9, 82, 10]
[...data]bikin salinan.sortmengubah array yang dia urutkan, jadi tanpa salinan,dataaslinya ikut berubah.(a, b) => a - badalah fungsi pembanding: hasil negatif artinyaadi depanb. Untuk angka, fungsi ini wajib ada.
Tabel perbandingan
Big-O bilang seberapa cepat kerja algoritma bertambah saat datanya bertambah. Untuk 1.000 angka: O(n) sekitar 1.000 langkah, O(n log n) sekitar 10.000, O(n²) sekitar 1.000.000.
| Sort | Terbaik | Rata-rata | Terburuk | Memori tambahan | Stabil |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Ya |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | Tidak |
| Insertion | O(n) | O(n²) | O(n²) | 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²) | O(log n) | Tidak |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | Tidak |
| Counting | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Ya |
- Terbaik biasanya data yang sudah terurut. Bubble sort cuma O(n) kalau pakai flag
swapped(berhenti begitu satu putaran gak menukar apa pun). - Memori tambahan O(1) artinya cuma beberapa variabel. Merge sort butuh array tambahan sebesar data, quick sort butuh catatan rekursi, counting sort butuh
kkotak hitungan (k = rentang nilai) plus array hasil. - Stabil artinya data yang nilainya sama tetap di urutan aslinya. Penting kalau kamu mengurutkan data, misalnya transaksi yang sudah urut tanggal diurutkan lagi berdasarkan jumlah.
Cara memilih
- Data kecil atau hampir terurut: insertion sort.
- Butuh stabil, atau waktu terburuk harus dijamin: merge sort.
- Data acak di memori, mau yang biasanya tercepat: quick sort, dengan pivot acak atau tengah.
- Memori sangat sempit dan waktu terburuk harus dijamin: heap sort.
- Bilangan bulat dengan rentang kecil: counting sort.
Di JavaScript, pakai arr.sort()
V8, mesin JavaScript di Chrome dan Node.js, memakai Timsort sejak 2018: campuran insertion sort untuk potongan kecil dan merge sort untuk menggabungkannya. Itu jawaban tebakannya. Timsort stabil, O(n log n) di kasus terburuk, dan cepat di data yang hampir terurut. Sejak ES2019, sort di semua browser wajib stabil. Jadi sehari-hari pakai arr.sort((a, b) => a - b). Menulis sort sendiri itu untuk belajar, atau untuk kasus khusus seperti counting sort.
⚠️ Jebakan yang sering ketemu
sort()tanpa fungsi pembanding.[3, 9, 10, 27].sort()hasilnya[10, 27, 3, 9], karena tanpa pembanding, angka diurutkan sebagai teks. Untuk angka, selalu tulis(a, b) => a - b.- Array asli ikut berubah.
sortmengurutkan array itu sendiri. Kalau aslinya masih dibutuhkan, urutkan salinannya:[...data].sort(...). - Lupa soal stabil. Selection, quick, dan heap sort bisa menukar urutan data yang nilainya sama. Kalau urutan itu penting, pakai merge sort atau
arr.sort().
TL;DR: Pilih sort berdasarkan datanya. Hampir terurut atau kecil: insertion sort, yang terbaiknya O(n). Butuh stabil atau jaminan O(n log n): merge sort, dengan memori tambahan O(n). Data acak: quick sort, rata-rata tercepat tapi O(n²) di kasus terburuk dan gak stabil. Memori sempit: heap sort. Bilangan bulat rentang kecil: counting sort, O(n + k). Di JavaScript, arr.sort((a, b) => a - b) memakai Timsort (insertion plus merge sort), yang stabil dan cepat.
