Radix Sort

Radix sort adalah algoritma sorting non-comparison yang memproses bilangan bulat digit demi digit. Alih-alih membandingkan elemen secara langsung, radix sort mengurutkan berdasarkan digit, dari digit paling tidak signifikan (LSD — least significant digit) atau paling signifikan (MSD — most significant digit). Setiap pass menggunakan stable counting sort pada satu digit. Kompleksitas total adalah O(d·(n + b)) dengan d = jumlah digit dan b = basis. Untuk bilangan 32-bit dengan basis 256, hanya 4 pass diperlukan — jauh lebih efisien daripada O(n log n) comparison sort. Pada Chapter ini kita akan membedah mekanisme radix sort LSD, mengimplementasikannya, dan membandingkan dengan radix sort MSD.

Aturan: Sort per Digit dengan Stable Sort #

Radix sort bekerja pada prinsip berikut: jika kita mengurutkan elemen berdasarkan digit paling signifikan (MSD) lebih dulu, lalu digit berikutnya, urutan digit pertama akan rusak. Namun bila kita mengurutkan dari digit paling tidak signifikan (LSD) ke paling signifikan, dan setiap pass adalah stable sort, maka hasil akhir benar — stabilitas menjaga urutan relatif dari pass sebelumnya.

Mekanisme LSD Radix Sort #

Setiap pass mengurutkan berdasarkan satu digit. Setelah pass ke-d, elemen terurut berdasarkan d digit paling tidak signifikan — yaitu, seluruh bilangan (asalkan d cukup besar untuk merepresentasikan nilai maksimum).

Kode: LSD Radix Sort #

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

void counting_sort_by_digit(std::vector<int>& v, int exp) {
    int n = static_cast<int>(v.size());
    std::vector<int> output(n);
    std::vector<int> count(10, 0);

    for (int x : v) {
        int digit = (x / exp) % 10;
        ++count[digit];
    }
    for (int i = 1; i < 10; ++i) count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; --i) {
        int digit = (v[i] / exp) % 10;
        output[--count[digit]] = v[i];
    }
    v = output;
}

void radix_sort_lsd(std::vector<int>& v) {
    if (v.empty()) return;
    int max_val = *std::max_element(v.begin(), v.end());
    for (int exp = 1; max_val / exp > 0; exp *= 10) {
        counting_sort_by_digit(v, exp);
        std::cout << "  setelah exp=" << exp << ": ";
        for (int x : v) std::cout << ' ' << x;
        std::cout << '\n';
    }
}

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

int main() {
    std::vector<int> a = {170, 45, 75, 90, 802, 24, 2, 66};
    std::cout << "Sebelum radix sort: "; print(a);
    std::cout << "Langkah-langkah:\n";
    radix_sort_lsd(a);
    std::cout << "Hasil akhir       : "; print(a);
    return 0;
}

Output yang Dihasilkan:

Sebelum radix sort:  170 45 75 90 802 24 2 66
Langkah-langkah:
  setelah exp=1:  170 90 802 2 24 45 75 66
  setelah exp=10:  802 2 24 45 66 170 75 90
  setelah exp=100:  2 24 45 66 75 90 170 802
Hasil akhir       :  2 24 45 66 75 90 170 802

Bedah Kode Baris-per-Baris #

1. void counting_sort_by_digit(std::vector<int>& v, int exp): counting sort yang beroperasi pada digit ke-exp. Untuk basis 10, exp = 1 berarti satuan, exp = 10 berarti puluhan, exp = 100 berarti ratusan.
2. int digit = (x / exp) % 10;: ekstrak digit pada posisi exp. Misalnya untuk x = 75, exp = 10: (75 / 10) % 10 = 7.
3. std::vector<int> count(10, 0);: array frekuensi untuk 10 digit (basis 10).
4. for (int x : v) ++count[digit];: hitung frekuensi setiap digit pada pass ini.
5. for (int i = 1; i < 10; ++i) count[i] += count[i - 1];: ubah ke cumulative count.
6. for (int i = n - 1; i >= 0; --i): iterasi mundur — krusial untuk stabilitas.
7. output[--count[digit]] = v[i];: tempatkan elemen pada posisi yang ditentukan cumulative count.
8. int max_val = *std::max_element(...);: nilai maksimum menentukan berapa pass diperlukan.
9. for (int exp = 1; max_val / exp > 0; exp *= 10): loop pass. Setiap pass mengalikan exp dengan 10 (basis). Loop berhenti ketika exp > max_val — semua digit sudah diproses.
10. Output exp=1: array diurutkan berdasarkan digit satuan: 170 (0), 90 (0), 802 (2), 2 (2), 24 (4), 45 (5), 75 (5), 66 (6). Stabilitas menjaga 170 sebelum 90 (keduanya berakhir digit 0).
11. Output exp=10: array diurutkan berdasarkan digit puluhan, tetapi stabilitas mempertahankan urutan satuan dari pass sebelumnya.
12. Output exp=100: array diurutkan berdasarkan digit ratusan, dengan stabilitas terhadap dua pass sebelumnya. Hasil akhir benar terurut.

Kompleksitas #

Dengan:

• d = jumlah digit maksimum (misalnya log_b(max_val)).
• n = jumlah elemen.
• b = basis (10 untuk desimal, 256 untuk byte, 65536 untuk word).

Memilih Basis b #

Basis yang lebih besar mengurangi jumlah pass d tetapi meningkatkan ukuran array count b:

• b = 10: d = log_10(max_val), count array ukuran 10. Untuk max_val = 10^9, d = 9.
• b = 256: d = 4 untuk 32-bit integer, count array ukuran 256.
• b = 65536: d = 2 untuk 32-bit, count array ukuran 65536 (256 KB).

Trade-off: basis besar mengurangi pass tetapi menambah memori dan mungkin menurunkan cache locality.

LSD vs MSD #

LSD (Least Significant Digit) #

Mulai dari digit paling kanan. Implementasi iteratif, stabil otomatis. Cocok untuk bilangan dengan panjang digit tetap.

MSD (Most Significant Digit) #

Mulai dari digit paling kiri. Setelah pass pertama, array terbagi menjadi bucket berdasarkan digit pertama. Tiap bucket direkursi radix sort pada digit berikutnya. MSD cocok untuk string (panjang variabel) karena dapat berhenti lebih awal bila bucket berukuran 1.

Stabilitas #

LSD radix sort stabil secara default karena setiap pass adalah stable counting sort. Stabilitas inilah yang membuat algoritma benar — bila salah satu pass tidak stabil, urutan digit sebelumnya akan rusak dan hasil akhir salah.

In-Place? #

Radix sort tidak in-place — membutuhkan O(n) memori tambahan untuk array output pada setiap pass. Beberapa varian in-place radix sort ada (misalnya American flag sort), tetapi implementasinya kompleks dan konstanta besar.

Mendukung Bilangan Negatif #

Implementasi di atas hanya untuk bilangan non-negatif. Untuk bilangan negatif, dua pendekatan:

1. Offset — geser semua nilai sehingga minimum menjadi 0, sort, lalu geser kembali.
2. Two’s complement trick — pada bilangan 32-bit two’s complement, interpretasi bit sebagai uint32_t menghasilkan urutan yang benar: bilangan negatif (0x80000000-0xFFFFFFFF) muncul setelah bilangan positif (0x00000000-0x7FFFFFFF). Lakukan radix sort pada uint32_t, lalu cast kembali.

Aplikasi #

• Mengurutkan NIK, NIP, nomor rekening — bilangan bulat panjang.
• Suffix array construction — algoritma DC3 memakai radix sort.
• Mengurutkan string panjang sama — misalnya kode pos, ISBN.
• Pengganti std::sort untuk n besar dengan rentang nilai terbatas — sering lebih cepat.

Komparasi: Radix Sort vs std::sort #

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>

void counting_sort_by_digit(std::vector<int>& v, int exp) {
    int n = static_cast<int>(v.size());
    std::vector<int> output(n);
    std::vector<int> count(256, 0);
    for (int x : v) ++count[(static_cast<unsigned>(x) >> (8 * exp)) & 0xFF];
    for (int i = 1; i < 256; ++i) count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; --i) {
        int d = (static_cast<unsigned>(v[i]) >> (8 * exp)) & 0xFF;
        output[--count[d]] = v[i];
    }
    v = output;
}

void radix_sort_256(std::vector<int>& v) {
    // Flip sign bit agar signed int terurut benar sebagai unsigned
    for (int& x : v) x = static_cast<int>(static_cast<unsigned>(x) ^ 0x80000000u);
    for (int exp = 0; exp < 4; ++exp) counting_sort_by_digit(v, exp);
    for (int& x : v) x = static_cast<int>(static_cast<unsigned>(x) ^ 0x80000000u);
}

int main() {
    std::mt19937 rng(42);
    const int N = 1'000'000;
    std::vector<int> a(N), b(N);
    for (int i = 0; i < N; ++i) a[i] = b[i] = static_cast<int>(rng());

    auto t1 = std::chrono::high_resolution_clock::now();
    radix_sort_256(a);
    auto t2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> d_rad = t2 - t1;

    t1 = std::chrono::high_resolution_clock::now();
    std::sort(b.begin(), b.end());
    t2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> d_std = t2 - t1;

    std::cout << "n = " << N << " integer acak:\n";
    std::cout << "  radix sort (basis 256): " << d_rad.count() << " ms\n";
    std::cout << "  std::sort             : " << d_std.count() << " ms\n";
    std::cout << "  hasil sama : " << (a == b ? "ya" : "tidak") << '\n';
    return 0;
}

Output yang Dihasilkan (waktu bervariasi antar mesin):

n = 1000000 integer acak:
  radix sort (basis 256): 35 ms
  std::sort             : 70 ms
  hasil sama : ya

1. Basis 256 (byte): 4 pass untuk 32-bit integer. Count array ukuran 256 — muat di L1 cache.
2. >> (8 * exp) dan & 0xFF: ekstrak byte ke-exp (0-3). Berbeda dengan basis 10 yang pakai division/modulo, bit-shift jauh lebih cepat.
3. x ^ 0x80000000u: flip sign bit agar signed int terurut benar sebagai unsigned. Tanpa trik ini, bilangan negatif (high bit set) akan muncul setelah bilangan positif.
4. Hasil: radix sort ~2× lebih cepat dari std::sort untuk integer 32-bit acak. Konstanta kecil dan akses sekuensial membuat radix sort unggul.

Ringkasan #

• Radix sort memproses bilangan bulat digit demi digit dengan stable counting sort per pass.
• Kompleksitas O(d·(n + b)) — d digit, basis b.
• Stabil — stabilitas adalah syarat mutlak untuk kebenaran algoritma.
• Tidak in-place — O(n + b) memori tambahan.
• LSD (iteratif sederhana) cocok untuk fixed-length keys; MSD (rekursif) cocok untuk variable-length keys.
• Untuk integer 32-bit, basis 256 memberikan 4 pass dengan count array muat di L1 cache — sering lebih cepat dari std::sort.

Pada chapter berikutnya kita akan membahas bucket sort — algoritma distribution-based yang menggabungkan ide radix (membagi ke bucket) dengan comparison sort di dalam bucket.