Penjelasan counting sort: cara kerja, kode, dan kompleksitas

Masalah apa yang diselesaikan counting sort

Setiap sort yang hanya membandingkan pasangan elemen membutuhkan Ω(n log n) perbandingan pada kasus terburuk. Counting sort menghindari batas ini dengan tidak membandingkan sama sekali: ia memakai kunci itu sendiri sebagai indeks array. Ketika kuncinya bilangan bulat kecil, seperti nilai ujian 0 sampai 100, usia, byte 0 sampai 255, atau rating bintang, cara ini lebih cepat daripada comparison sort mana pun.

Harganya adalah memori yang sebanding dengan rentang kunci. Mengurutkan segelintir bilangan bulat 64-bit yang tersebar di seluruh rentang akan membutuhkan array hitungan yang sangat besar dan tidak realistis.

Ide dan contoh langkah demi langkah

Urutkan [4, 2, 2, 8, 3, 3, 1], yang nilainya berada pada rentang 0 sampai 8 (k = 9).

1. Hitung setiap nilai: count[v] adalah berapa kali v muncul.
2. Prefix sum: ganti setiap hitungan dengan jumlah elemen yang kurang dari atau sama dengan nilai itu. Maka count[v] adalah satu posisi setelah posisi terakhir tempat v berada.
3. Tempatkan elemen: telusuri input dari kanan ke kiri; untuk setiap nilai v, kurangi count[v] lalu tulis v di posisi itu. Menelusuri dari kanan ke kiri menjaga nilai yang sama tetap dalam urutan aslinya.

Jadi angka 1 masuk ke indeks 0, dua angka 2 ke indeks 1 dan 2, dua angka 3 ke indeks 3 dan 4, angka 4 ke indeks 5, dan angka 8 ke indeks 6. Hasil: [1, 2, 2, 3, 3, 4, 8].

Implementasi Python

Versi stabil ini mengurutkan objek apa pun berdasarkan kunci bilangan bulat antara 0 dan k - 1.

def counting_sort(items, k, key=lambda x: x):
    """Stable sort of items by integer key in range(k)."""
    count = [0] * k
    for x in items:
        count[key(x)] += 1
    for v in range(1, k):                # prefix sums
        count[v] += count[v - 1]
    out = [None] * len(items)
    for x in reversed(items):            # right to left: stable
        count[key(x)] -= 1
        out[count[key(x)]] = x
    return out

print(counting_sort([4, 2, 2, 8, 3, 3, 1], k=9))
# [1, 2, 2, 3, 3, 4, 8]
people = [("Ana", 3), ("Bo", 1), ("Cy", 3), ("Di", 2)]
print(counting_sort(people, k=4, key=lambda p: p[1]))
# [('Bo', 1), ('Di', 2), ('Ana', 3), ('Cy', 3)]

Ketika Anda hanya mengurutkan bilangan bulat biasa dan tidak butuh stabilitas, versi yang lebih sederhana membangun ulang output dari hitungan. Varian ini juga menangani bilangan negatif dengan menggeser sebesar nilai minimum:

def counting_sort_ints(nums):
    if not nums:
        return []
    lo, hi = min(nums), max(nums)
    count = [0] * (hi - lo + 1)
    for x in nums:
        count[x - lo] += 1
    out = []
    for offset, c in enumerate(count):
        out.extend([offset + lo] * c)
    return out

print(counting_sort_ints([3, -1, 2, -1, 0]))   # [-1, -1, 0, 2, 3]

Kompleksitas waktu dan ruang

Counting sort bersifat linear ketika k adalah O(n). Jika k jauh lebih besar daripada n, misalnya 1.000 nilai dalam rentang 0 sampai 10⁹, array hitungan mendominasi dan comparison sort atau radix sort lebih baik.

Perbandingan counting sort dengan sort lain

Di sini k adalah ukuran rentang kunci, d jumlah digit, dan b basis yang dipakai radix sort. Counting sort stabil ketika elemen ditempatkan memakai prefix sum dari kanan ke kiri. Versi sederhana yang membangun ulang dari hitungan menghasilkan hasil yang sama untuk bilangan bulat biasa tetapi tidak bisa membawa data lain bersama kuncinya.

Varian dan kesalahan umum

• Radix sort menjalankan counting sort yang stabil satu kali per digit, yang memperluas ide ini ke bilangan bulat besar dan string dengan panjang tetap.
• Bucket sort menyebarkan nilai ke bucket menurut rentang lalu mengurutkan setiap bucket; cepat ketika nilai tersebar merata.
• Menghitung tanpa mengurutkan: sering kali Anda hanya butuh hitungannya, misalnya untuk membuat histogram atau mencari modus. collections.Counter melakukannya secara langsung.

Kapan memakai counting sort

Pakai ketika kuncinya bilangan bulat dalam rentang yang kecil dibandingkan jumlah elemen: nilai ujian, usia, tanggal dalam bulan, byte, nilai kanal warna 0 sampai 255, atau nilai enum kecil. Ini juga langkah dalam radix sort dan algoritma pembangun suffix array. Dalam wawancara, ia muncul pada soal seperti sort colors (nilai 0, 1, 2), pengurutan berdasarkan frekuensi, dan H-index, serta pada pertanyaan klasik tentang cara menembus batas O(n log n) untuk comparison sort.