Materi
Urut gabung dan sorted() bekerja dengan membandingkan dua data. Urut hitung (counting sort) tidak membandingkan sama sekali. Syaratnya, kunci pengurutannya bilangan bulat dalam rentang kecil yang diketahui, misalnya nilai kuis 0 sampai 10 atau bintang ulasan 1 sampai 5. Disiapkan satu larik penghitung dengan satu kotak untuk setiap kemungkinan nilai, lalu data dibaca sekali dan kotak nilainya ditambah satu.
Setelah semua dihitung, hasil disusun dengan membaca larik penghitung dari nilai terkecil ke terbesar dan menuliskan setiap nilai sebanyak isi kotaknya. Biayanya O(n + k): n untuk membaca data dan k untuk membaca larik penghitung yang berukuran sebanyak rentang nilai. Ketika k kecil dibanding n, urut hitung lebih cepat daripada pengurutan dengan perbandingan.
Contoh: nilai kuis delapan siswa 3, 0, 2, 3, 1, 2, 3, 0 dengan rentang 0–3. Larik penghitungnya [2, 1, 2, 3], dibaca jadi 0, 0, 1, 2, 2, 3, 3, 3. Untuk data bercatatan seperti ulasan yang punya nama, setiap kotak berisi daftar catatan, bukan angka. Catatan dimasukkan sesuai urutan datang, sehingga urut hitung stabil: catatan berkunci sama keluar dalam urutan aslinya.
from collections import Counter
nilai = [3, 0, 2, 3, 1, 2, 3, 0]
print(Counter(nilai)) # Counter({3: 3, 0: 2, 2: 2, 1: 1})
