Counting sort mengurutkan bilangan bulat tanpa pernah membandingkan dua angka: dia menghitung berapa kali tiap nilai muncul, lalu menyusun hasilnya dari hitungan itu. Mirip menghitung suara pakai turus: tiap pilihan punya satu kolom, dan hasil akhirnya tinggal dibaca dari kolom pertama sampai terakhir. Syaratnya, angkanya bilangan bulat yang gak negatif, dengan rentang nilai yang kecil.
🧪 Tebakan cepat: untuk mengurutkan
[4, 2, 2, 8, 3, 3, 1], berapa kotak hitungan yang dibutuhkan: 7 (banyaknya angka) atau 9? Tebak dulu, jawabannya ada di bagian "Hitung, akumulasi, susun".
Hitung, akumulasi, susun
Counting sort punya satu array bantu, count, dengan satu kotak untuk tiap nilai dari 0 sampai angka terbesar. Ini yang terjadi pada [4, 2, 2, 8, 3, 3, 1]:
| Fase | Yang dikerjakan | Hasilnya |
|---|---|---|
| 1. Hitung | tiap angka menambah kotaknya sendiri: angka 4 menambah count[4] |
count = [0, 1, 2, 2, 1, 0, 0, 0, 1] |
| 2. Akumulasi | tiap kotak ditambah kotak sebelumnya | count = [0, 1, 3, 5, 6, 6, 6, 6, 7] |
| 3. Susun | baca input dari kanan: 1 ke index 0, 3 ke index 4, 3 ke index 3, dan seterusnya | [1, 2, 2, 3, 3, 4, 8] |
function countingSort(arr) {
const max = Math.max(...arr);
const count = new Array(max + 1).fill(0); // max + 1 kotak
// 1. Hitung: count[v] = berapa kali v muncul
for (const v of arr) count[v]++;
// 2. Akumulasi: count[v] = banyaknya angka <= v
for (let v = 1; v <= max; v++) count[v] += count[v - 1];
// 3. Susun output, dari kanan supaya stabil
const output = new Array(arr.length);
for (let i = arr.length - 1; i >= 0; i--) {
count[arr[i]]--;
output[count[arr[i]]] = arr[i];
}
return output;
}
console.log(countingSort([4, 2, 2, 8, 3, 3, 1]));
// [1, 2, 2, 3, 3, 4, 8]
Math.max(...arr)mencari angka terbesar, 8.new Array(max + 1).fill(0)bikin 9 kotak berisi 0, index 0 sampai 8. Jawaban tebakan: 9, karena jumlah kotak ikut nilai terbesar, bukan banyaknya angka.count[v]++: angkanya sendiri jadi alamat kotak. Gak ada perbandingan antar angka sama sekali.- Setelah akumulasi,
count[3]= 5 artinya ada 5 angka yang kurang dari atau sama dengan 3, jadi angka 3 yang terakhir duduk di index 4. - Fase 3 mengurangi kotaknya satu, lalu menaruh angka di index itu. Jalan dari kanan membuat angka yang sama tetap di urutan aslinya, alias stabil. Ini penting kalau yang diurutkan adalah data, misalnya siswa berdasarkan nilainya.
Kalau isinya cuma angka, ada jalan pintas: setelah fase 1, tulis tiap nilai sebanyak hitungannya. count[1] = 1, count[2] = 2, count[3] = 2, count[4] = 1, count[8] = 1 langsung jadi [1, 2, 2, 3, 3, 4, 8].
Kapan counting sort menang
Big-O bilang seberapa cepat kerja algoritma bertambah saat datanya bertambah. O(n) artinya datanya dua kali lipat, waktunya kira-kira dua kali lipat.
Counting sort O(n + k): n adalah banyaknya angka, k adalah banyaknya kotak (rentang nilai). Sort yang membandingkan, seperti merge sort dan quick sort, butuh sekitar O(n log n).
- k kecil dibanding n: menang. Nilai ujian 0 sampai 100 untuk 1.000 siswa: sekitar 1.000 + 101 langkah, sedangkan n log n sekitar 10.000.
- k besar: boros.
[5, 1000000]cuma 2 angka, tapi butuh sejuta kotak. - Bukan bilangan bulat: gak bisa langsung. Angka desimal, angka negatif, dan teks gak bisa jadi index kotak.
⚠️ Jebakan yang sering ketemu
- Kotak kurang satu.
new Array(max)cuma punya index 0 sampaimax - 1, jadi angka terbesar gak punya kotak. Harusmax + 1. - Angka negatif.
count[-1]gak ada. Geser dulu semua angka, misalnya kurangi dengan angka terkecil, lalu kembalikan saat menyusun. - Fase 3 dari kiri. Hasilnya tetap terurut, tapi angka yang sama tertukar urutannya, jadi sort-nya gak stabil lagi.
TL;DR: Counting sort menghitung berapa kali tiap nilai muncul di array count (satu kotak per nilai, dari 0 sampai yang terbesar, jadi max + 1 kotak), mengakumulasi hitungannya, lalu menaruh tiap angka di posisinya, dari kanan supaya stabil. Untuk angka saja, cukup tulis tiap nilai sebanyak hitungannya. Waktunya O(n + k), jadi menang kalau rentang nilai k kecil dibanding n, misalnya nilai ujian 0 sampai 100. Cuma untuk bilangan bulat yang gak negatif.
