Pengenalan counting sort

Counting sort adalah pengurutan yang bekerja tanpa satu pun perbandingan antarelemen. Ia menghitung berapa kali setiap nilai muncul, mengubah hitungan itu menjadi posisi, lalu menempatkan setiap elemen langsung ke posisinya. Topik ini membangun versi stabilnya dalam tiga langkah dengan Python dan Java, membaca keluarannya baris demi baris, serta menetapkan kapan pengurutan ini menang dan kapan ia justru boros.

Pengurutan tanpa perbandingan#

Semua pengurutan yang bekerja lewat perbandingan membawa batas bawah $\Omega(n \log n)$, karena setiap perbandingan hanya memisahkan kemungkinan menjadi dua cabang, dan $n!$ urutan yang mungkin harus dapat dibedakan. Counting sort tidak memainkan permainan itu. Kunci yang dihitung dipakai langsung sebagai indeks array, sehingga tidak ada cabang keputusan yang perlu dijelajahi dan batas bawah perbandingan tersebut tidak berlaku padanya.

Biayanya dinyatakan $O(n + k)$ waktu dengan $k$ sebagai rentang nilai yang mungkin, ditambah $O(n + k)$ memori untuk array frekuensi dan array hasil. Ketika $k$ kecil dan sebanding dengan $n$, angka itu menyamai bahkan mengalahkan $O(n \log n)$. Ketika $k$ membengkak, biaya memorinya yang menjadi masalah utama. Perhitungan sederhana inilah yang menentukan kapan counting sort layak dipilih, dan pembahasannya ditutup di bagian akhir topik.

Tiga langkah menuju hasil terurut#

Langkah pertama menghitung frekuensi setiap nilai pada array berukuran $k$. Langkah kedua menjumlahkannya secara prefiks, sehingga setiap sel menyimpan indeks terakhir nilai itu pada hasil. Langkah ketiga menempatkan elemen dari belakang ke depan sambil menurunkan hitungan sebelum menulis, sehingga elemen duplikat menduduki posisi sesuai urutan asalnya dan hasilnya menjadi stabil.

"""Counting sort tiga langkah: frekuensi, jumlah prefiks, dan penempatan stabil."""


def hitung_frekuensi(data, kunci=lambda elemen: elemen, rentang=10):
    """Hitung berapa kali setiap kunci muncul, tanpa membandingkan elemen."""
    frekuensi = [0] * rentang
    for elemen in data:
        frekuensi[kunci(elemen)] += 1
    return frekuensi


def jumlah_prefiks(frekuensi):
    """Ubah frekuensi menjadi indeks terakhir setiap kunci pada hasil."""
    posisi = list(frekuensi)
    for i in range(1, len(posisi)):
        posisi[i] += posisi[i - 1]
    return posisi


def counting_sort(data, kunci=lambda elemen: elemen, rentang=10):
    """Urutkan naik dengan menempatkan elemen dari belakang agar stabil."""
    posisi = jumlah_prefiks(hitung_frekuensi(data, kunci, rentang))
    hasil = [0] * len(data)
    for elemen in reversed(data):
        k = kunci(elemen)
        posisi[k] -= 1
        hasil[posisi[k]] = elemen
    return hasil


if __name__ == "__main__":
    data = [4, 2, 9, 6, 2, 0, 7, 4, 2]
    print("data    :", data)
    frekuensi = hitung_frekuensi(data)
    print("frek    :", frekuensi)
    print("prefiks :", jumlah_prefiks(frekuensi))
    print("hasil   :", counting_sort(data))

    # kestabilan: dua nilai 7 dan dua nilai 2 membawa penanda huruf
    berlabel = [(7, "a"), (2, "b"), (7, "c"), (2, "d")]
    hasil = counting_sort(berlabel, kunci=lambda pasangan: pasangan[0])
    print("stabil  :", hasil)

data    : [4, 2, 9, 6, 2, 0, 7, 4, 2]
frek    : [1, 0, 3, 0, 2, 0, 1, 1, 0, 1]
prefiks : [1, 1, 4, 4, 6, 6, 7, 8, 8, 9]
hasil   : [0, 2, 2, 2, 4, 4, 6, 7, 9]
stabil  : [(2, 'b'), (2, 'd'), (7, 'a'), (7, 'c')]

Keluaran memperlihatkan ketiga langkah secara berurutan. Baris frekuensi menyatakan nilai 2 muncul tiga kali, nilai 4 dua kali, dan nilai 9 satu kali. Baris prefiks mengubahnya menjadi indeks terakhir pada hasil. Misalnya, angka 4 pada sel keempat berarti nilai 2 menempati indeks 0 sampai 3, yaitu satu elemen yang lebih kecil dari 2 ditambah tiga salinannya. Penempatan berjalan dari belakang dan menurunkan hitungan sebelum menulis, sehingga salinan 2 yang asalnya lebih kanan tetap mendarat lebih kanan.

Baris terakhir menguji kestabilan dengan empat pasangan nilai dan penanda huruf. Dua nilai 7 dan dua nilai 2 bergeser sesuai nilainya, tetapi penandanya tetap dalam urutan asal, a sebelum c dan b sebelum d. Invarian itu penting ketika pengurutan dilakukan bertahap, misalnya mengurutkan menurut nilai lalu menurut nama, karena urutan tahap sebelumnya tidak boleh terhapus.

Versi Java#

Versi Java memakai struktur yang sama dengan konstanta RENTANG sebagai ukuran array frekuensi. Penempatan dari belakang dituliskan sebagai perulangan indeks yang berjalan mundur, dan array hasil dialokasikan sekali dengan ukuran masukan. Empat baris keluarannya identik dengan empat baris pertama versi Python karena algoritma dan datanya sama persis.

import java.util.Arrays;

public class CountingSort {

    static final int RENTANG = 10;   // nilai yang sah berada di 0 sampai 9

    // langkah 1: hitung berapa kali setiap nilai muncul, tanpa perbandingan
    static int[] hitungFrekuensi(int[] data) {
        int[] frekuensi = new int[RENTANG];
        for (int nilai : data) {
            frekuensi[nilai]++;
        }
        return frekuensi;
    }

    // langkah 2: ubah frekuensi menjadi indeks terakhir setiap nilai pada hasil
    static int[] jumlahPrefiks(int[] frekuensi) {
        int[] posisi = frekuensi.clone();
        for (int i = 1; i < posisi.length; i++) {
            posisi[i] += posisi[i - 1];
        }
        return posisi;
    }

    // langkah 3: tempatkan elemen dari belakang agar hasilnya stabil
    static int[] countingSort(int[] data) {
        int[] posisi = jumlahPrefiks(hitungFrekuensi(data));
        int[] hasil = new int[data.length];
        for (int i = data.length - 1; i >= 0; i--) {
            int nilai = data[i];
            posisi[nilai]--;
            hasil[posisi[nilai]] = nilai;
        }
        return hasil;
    }

    public static void main(String[] args) {
        int[] data = {4, 2, 9, 6, 2, 0, 7, 4, 2};
        System.out.println("data    : " + Arrays.toString(data));
        int[] frekuensi = hitungFrekuensi(data);
        System.out.println("frek    : " + Arrays.toString(frekuensi));
        System.out.println("prefiks : " + Arrays.toString(jumlahPrefiks(frekuensi)));
        System.out.println("hasil   : " + Arrays.toString(countingSort(data)));
    }
}

data    : [4, 2, 9, 6, 2, 0, 7, 4, 2]
frek    : [1, 0, 3, 0, 2, 0, 1, 1, 0, 1]
prefiks : [1, 1, 4, 4, 6, 6, 7, 8, 8, 9]
hasil   : [0, 2, 2, 2, 4, 4, 6, 7, 9]

# menjalankan berkas Java tunggal tanpa tahap kompilasi terpisah
java CountingSort.java

data    : [4, 2, 9, 6, 2, 0, 7, 4, 2]
frek    : [1, 0, 3, 0, 2, 0, 1, 1, 0, 1]
prefiks : [1, 1, 4, 4, 6, 6, 7, 8, 8, 9]
hasil   : [0, 2, 2, 2, 4, 4, 6, 7, 9]

Kapan menang dan kapan buruk#

Counting sort menang ketika rentang nilainya kecil dan padat. Nilai ujian 0 sampai 100, usia dalam tahun, atau nilai huruf yang dipetakan ke angka 0 sampai 4 adalah contoh alaminya. Pada kasus seperti ini, $k$ yang kecil membuat array frekuensinya pendek dan total sapuannya hanya sedikit lebih dari satu kali panjang data. Pengurutan perbandingan mana pun tidak mampu menandingi biaya yang hampir linear pada kasus semacam ini.

Keadaan berbalik ketika rentangnya lebar. Mengurutkan jutaan bilangan yang tersebar dari 0 sampai satu miliar menuntut array frekuensi sebesar rentang itu, padahal jumlah elemennya jauh lebih kecil, sehingga memori terbuang untuk sel yang hampir semuanya kosong. Nilai desimal, string, atau bilangan negatif juga tidak dapat dipakai sebagai indeks tanpa penyesuaian, misalnya menggeser seluruh nilai dengan offset nilai minimum agar kembali berada di 0 sampai $k-1$.

Kesalahan umum#

1. Ukuran array frekuensi kurang satu. Nilai maksimum 9 menuntut array berukuran 10, bukan 9, karena indeks harus menjangkau nilai itu sendiri. Bila offset dipakai, ukurannya adalah maksimum dikurangi minimum ditambah satu, dan kelalaian ini berujung error indeks di luar batas.
2. Menempatkan elemen dari depan. Iterasi maju dengan hasil prefiks membuat duplikat menduduki posisi terbalik dari asalnya, sehingga kestabilan hilang tanpa pesan apa pun. Penempatan harus berjalan dari belakang ke depan.
3. Memakai frekuensi sebagai posisi jadi. Hasil langkah pertama hanyalah hitungan, bukan lokasi. Tanpa jumlah prefiks, penempatan tidak memiliki titik acuan dan hasilnya kacau, kesalahan yang paling sering muncul saat menulis counting sort pertama kali.

Ringkasan#

• Counting sort tidak membandingkan elemen, melainkan menghitung frekuensi setiap nilai, sehingga batas bawah $\Omega(n \log n)$ pengurutan perbandingan tidak berlaku padanya.
• Alurnya tiga langkah, frekuensi, jumlah prefiks, dan penempatan mundur, dengan biaya $O(n + k)$ waktu dan memori.
• Penempatan dari belakang menjadikan hasilnya stabil, duplikat mempertahankan urutan asalnya.
• Ia menang pada rentang kecil seperti nilai ujian 0 sampai 100 dan boros pada rentang lebar karena array frekuensinya ikut membesar.

Referensi#

• Counting sort — Wikipedia — alur frekuensi, jumlah prefiks, dan penempatan pada counting sort beserta analisis biayanya.
• Comparison sort — Wikipedia — penjelasan batas bawah $\Omega(n \log n)$ untuk pengurutan yang bekerja lewat perbandingan.