Counting Sort

Counting sort adalah algoritma sorting non-comparison yang bekerja dengan menghitung frekuensi setiap nilai lalu merekonstruksi array terurut. Algoritma ini mencapai kompleksitas O(n + k) — n elemen ditambah k rentang nilai — yang menjadi O(n) bila k = O(n). Tidak seperti algoritma comparison-based yang dibatasi Ω(n log n), counting sort dapat mengalahkan batas ini untuk data dengan rentang kecil. Pada Chapter ini kita akan membedah mekanisme counting sort, mengimplementasikan versi stabil dengan cumulative count, dan menjelaskan kapan counting sort unggul. Pada akhir chapter kita akan paham mengapa counting sort menjadi sub-rutin untuk radix sort.

Aturan: Hitung, Akumulasi, Rekonstruksi #

Counting sort mengasumsikan input berupa bilangan bulat non-negatif dalam rentang [0, k). Algoritma bekerja dalam tiga fase:

1. Count — hitung frekuensi setiap nilai x ke dalam count[x].
2. Cumulative — ubah count menjadi cumulative count: count[i] sekarang menyatakan jumlah elemen ≤ i.
3. Build output — iterasi mundur pada input, tempatkan setiap elemen pada posisi count[x] - 1, lalu dekrementasi count[x].

Mekanisme Kerja #

Iterasi mundur pada langkah 3 krusial untuk stabilitas: elemen equal yang muncul lebih akhir di input akan ditempatkan setelah elemen equal yang muncul lebih awal — urutan relatif terjaga.

Kode: Counting Sort Stabil #

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

void counting_sort(std::vector<int>& v) {
    if (v.empty()) return;
    int k = *std::max_element(v.begin(), v.end()) + 1;
    std::vector<int> count(k, 0);
    for (int x : v) ++count[x];

    // Cumulative count
    for (int i = 1; i < k; ++i) count[i] += count[i - 1];

    // Build output (iterasi mundur untuk stabilitas)
    std::vector<int> output(v.size());
    for (int i = static_cast<int>(v.size()) - 1; i >= 0; --i) {
        int x = v[i];
        output[--count[x]] = x;
    }
    v = output;
}

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

int main() {
    std::vector<int> a = {4, 2, 2, 8, 3, 3, 1, 0, 4, 6, 1, 9, 5};
    std::cout << "Sebelum : "; print(a);
    counting_sort(a);
    std::cout << "Setelah : "; print(a);
    return 0;
}

Output yang Dihasilkan:

Sebelum :  4 2 2 8 3 3 1 0 4 6 1 9 5
Setelah :  0 1 1 2 2 3 3 4 4 5 6 8 9

Bedah Kode Baris-per-Baris #

1. int k = *std::max_element(v.begin(), v.end()) + 1;: rentang nilai adalah [0, k). Ukuran array count adalah k. Bila elemen minimum bukan 0, kita perlu menggeser (lihat variasi di bawah).
2. std::vector<int> count(k, 0);: array frekuensi, awalnya semua 0.
3. for (int x : v) ++count[x];: hitung frekuensi setiap nilai. Setelah loop, count[i] menyatakan jumlah elemen bernilai i.
4. for (int i = 1; i < k; ++i) count[i] += count[i - 1];: ubah menjadi cumulative count. Setelah loop, count[i] menyatakan jumlah elemen ≤ i — sekaligus indeks setelah elemen terakhir bernilai i pada output.
5. for (int i = static_cast<int>(v.size()) - 1; i >= 0; --i): iterasi mundur pada input. Mundur krusial untuk stabilitas.
6. output[--count[x]] = x;: tempatkan x pada posisi count[x] - 1 (dekremen dulu karena indeks 0-based). Setelah penempatan, count[x] berkurang — sehingga elemen equal berikutnya (yang muncul lebih awal di input) akan menempati posisi sebelumnya.
7. v = output;: ganti isi v dengan array output yang terurut.

Verifikasi Stabilitas #

Untuk membuktikan stabilitas, kita sort struct dengan key berupa bilangan bulat. Elemen dengan tag ("Andi", "Citra", …) menandai urutan input — bila setelah sorting tag masih berurutan untuk key yang sama, algoritma stabil.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

struct Item { int key; std::string tag; };

void counting_sort_items(std::vector<Item>& v) {
    if (v.empty()) return;
    int k = 0;
    for (const auto& it : v) k = std::max(k, it.key + 1);
    std::vector<int> count(k, 0);
    for (const auto& it : v) ++count[it.key];
    for (int i = 1; i < k; ++i) count[i] += count[i - 1];

    std::vector<Item> output(v.size());
    for (int i = static_cast<int>(v.size()) - 1; i >= 0; --i) {
        output[--count[v[i].key]] = v[i];
    }
    v = output;
}

int main() {
    std::vector<Item> items = {
        {3, "Andi"}, {1, "Budi"}, {3, "Citra"}, {2, "Dewi"},
        {1, "Eka"}, {3, "Fani"}, {2, "Gita"}
    };
    counting_sort_items(items);
    std::cout << "Stabilitas struct (lihat urutan tag dengan key sama):\n";
    for (const auto& it : items) std::cout << "  key=" << it.key << " tag=" << it.tag << '\n';
    return 0;
}

Output yang Dihasilkan:

Stabilitas struct (lihat urutan tag dengan key sama):
  key=1 tag=Budi
  key=1 tag=Eka
  key=2 tag=Dewi
  key=2 tag=Gita
  key=3 tag=Andi
  key=3 tag=Citra
  key=3 tag=Fani

1. output[--count[v[i].key]] = v[i];: tempatkan seluruh struct (bukan hanya key) ke output — inilah mengapa counting sort dapat stabil untuk data non-trivial.
2. Output key=1: Budi (input ke-2) tetap di depan Eka (input ke-5). Urutan input terjaga.
3. Output key=3: Andi, Citra, Fani — semua dengan key=3 — muncul dalam urutan input. Stabilitas terbukti.

Kompleksitas #

Kapan Counting Sort Lebih Cepat dari O(n log n) #

Counting sort menjadi O(n) ketika k = O(n). Misalnya:

• Mengurutkan nilai ujian [0, 100] untuk n = 1000 siswa → k = 101, n + k ≈ n.
• Mengurutkan IP address [0, 255] untuk n = 10.000 → k = 256, n + k ≈ n.

Sebaliknya, bila k >> n (misalnya mengurutkan 10 nomor NIK dengan 16 digit), counting sort menjadi sangat tidak efisien — k = 10^16 array count mustahil dialokasikan.

Variasi: Menggeser Rentang #

Bila elemen minimum bukan 0 (misalnya [1000, 5000]), gunakan offset:

void counting_sort_range(std::vector<int>& v) {
    if (v.empty()) return;
    int lo = *std::min_element(v.begin(), v.end());
    int hi = *std::max_element(v.begin(), v.end());
    int k = hi - lo + 1;
    std::vector<int> count(k, 0);
    for (int x : v) ++count[x - lo];             // shift ke [0, k)
    for (int i = 1; i < k; ++i) count[i] += count[i - 1];

    std::vector<int> output(v.size());
    for (int i = static_cast<int>(v.size()) - 1; i >= 0; --i) {
        int x = v[i];
        output[--count[x - lo]] = x;
    }
    v = output;
}

1. int lo = *std::min_element(...);: nilai minimum — dipakai sebagai offset.
2. count[x - lo]: indeks dalam array count di-shift sehingga minimum dipetakan ke indeks 0.
3. k = hi - lo + 1: ukuran array count sekarang hanya selisih max-min, bukan nilai absolut.

Mengapa Counting Sort Tidak Menggantikan std::sort #

Meskipun secara asimptotik O(n) dapat mengalahkan O(n log n), counting sort memiliki keterbatasan:

1. Hanya untuk bilangan bulat — tidak bisa langsung untuk float, string, atau struct tanpa key numerik.
2. Memori O(k) — bila k besar (misalnya 10^9), alokasi tidak feasible.
3. Tidak comparison-based — tidak menghormati comparator custom.

Sub-rutin untuk Radix Sort #

Counting sort menjadi sub-rutin penting untuk radix sort — algoritma non-comparison yang mengurutkan bilangan bulat besar dengan memproses digit demi digit. Setiap pass radix sort menggunakan counting sort pada satu digit (basis b). Stabilitas counting sort krusial: tanpa stabilitas, urutan relatif digit sebelumnya akan rusak.

Aplikasi #

• Mengurutkan usia, nilai ujian, IP address — rentang kecil, k = O(n).
• Sub-rutin radix sort — per-digit stable sort.
• Histogram equalization — pengolahan citra.
• Bucket distribution — awal bucket sort.
• Counting distinct values — counting sort secara langsung memberi frekuensi.

Ringkasan #

• Counting sort adalah algoritma non-comparison O(n + k) untuk bilangan bulat dengan rentang kecil.
• Tiga fase: hitung frekuensi, ubah ke cumulative, bangun output dengan iterasi mundur.
• Stabil — iterasi mundur pada build menjaga urutan relatif elemen equal.
• Tidak in-place — membutuhkan O(n + k) memori tambahan.
• Menjadi O(n) ketika k = O(n).
• Sub-rutin penting untuk radix sort.

Pada chapter berikutnya kita akan membahas radix sort — algoritma yang memperluas counting sort untuk bilangan bulat besar dengan memproses digit demi digit.