Bucket Sort

Bucket sort adalah algoritma sorting distribution-based yang membagi elemen ke dalam beberapa bucket berdasarkan nilai, mengurutkan tiap bucket, lalu menggabungkan hasilnya. Algoritma ini sangat efektif ketika data terdistribusi seragam — setiap bucket berukuran kecil sehingga sorting internal menjadi cepat. Expected time complexity adalah O(n + k) untuk n elemen dan k bucket, dengan worst case O(n²) bila semua elemen jatuh di satu bucket. Pada Chapter ini kita akan membedah mekanisme distribusi bucket, mengimplementasikannya dalam C++, dan menjelaskan kapan bucket sort unggul. Pada akhir chapter kita akan paham mengapa bucket sort menjadi pilihan untuk data numerik kontinu yang terdistribusi seragam.

Aturan: Distribusi, Sort per Bucket, Concatenate #

Bucket sort bekerja dalam tiga fase:

Distribusi — bagi elemen ke k bucket berdasarkan nilai. Untuk data [0, 1), elemen x masuk ke bucket ⌊k·x⌋.
Sort per bucket — urutkan tiap bucket dengan algoritma sederhana (insertion sort stabil, atau std::stable_sort).
Concatenate — gabungkan semua bucket secara berurutan.

Mekanisme Distribusi #

flowchart LR A["Input: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]"] --> B0["bucket 0: [0.17, 0.12]"] A --> B1["bucket 1: [0.26, 0.21, 0.23]"] A --> B2["bucket 2: [0.39]"] A --> B3["bucket 3: --"] A --> B4["bucket 4: --"] A --> B5["bucket 5: --"] A --> B6["bucket 6: [0.68, 0.72]"] A --> B7["bucket 7: [0.78]"] A --> B8["bucket 8: --"] A --> B9["bucket 9: [0.94]"] B0 --> C["sort masing-masing bucket"] B1 --> C B2 --> C B6 --> C B7 --> C B9 --> C C --> D["Concatenate: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]"]

Dengan n = 10 bucket, setiap bucket menampung elemen pada interval [i/10, (i+1)/10). Elemen 0.78 masuk bucket ⌊10·0.78⌋ = 7. Elemen 0.94 masuk bucket 9. Karena data seragam, setiap bucket berisi paling banyak ~1 elemen — sorting internal nyaris gratis.

Kode: Bucket Sort #

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

void bucket_sort(std::vector<double>& v) {
    int n = static_cast<int>(v.size());
    if (n < 2) return;

    std::vector<std::vector<double>> buckets(n);
    for (double x : v) {
        int idx = static_cast<int>(n * x);
        if (idx == n) idx = n - 1;  // safety: x == 1.0
        buckets[idx].push_back(x);
    }
    for (auto& b : buckets) std::stable_sort(b.begin(), b.end());
    int k = 0;
    for (auto& b : buckets) {
        for (double x : b) v[k++] = x;
    }
}

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

int main() {
    std::vector<double> v = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
    std::cout << "Sebelum: "; print(v);
    bucket_sort(v);
    std::cout << "Setelah: "; print(v);
    return 0;
}

Output yang Dihasilkan:

text

Sebelum:  0.78 0.17 0.39 0.26 0.72 0.94 0.21 0.12 0.23 0.68
Setelah:  0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94

Bedah Kode Baris-per-Baris #

std::vector<std::vector<double>> buckets(n);: alokasi n bucket kosong. Jumlah bucket = jumlah elemen — pilihan umum untuk distribusi seragam.
for (double x : v): iterasi setiap elemen input.
int idx = static_cast<int>(n * x);: hitung indeks bucket. Untuk x ∈ [0, 1), n·x ∈ [0, n), sehingga idx ∈ [0, n-1].
if (idx == n) idx = n - 1;: penanganan kasus edge — x sedikit lebih kecil dari 1.0 tetapi pembulatan bisa menghasilkan idx = n karena floating point.
buckets[idx].push_back(x);: tambahkan elemen ke bucket yang sesuai.
for (auto& b : buckets) std::stable_sort(b.begin(), b.end());: urutkan tiap bucket. std::stable_sort dipilih agar bucket sort tetap stabil. Pada bucket berukuran sangat kecil (< 16), insertion sort juga akan baik.
int k = 0; for (auto& b : buckets) for (double x : b) v[k++] = x;: concatenate — gabungkan semua bucket kembali ke v secara berurutan. Karena bucket sudah terurut berdasarkan indeks, output juga terurut secara global.

Kompleksitas #

Kasus	Kompleksitas	Penjelasan
Best (uniform)	`O(n + k)`	Setiap bucket berisi 1 elemen — sort gratis
Average (uniform)	`O(n + k)`	Bucket berukuran `O(n/k)` — sort internal `O((n/k)²)` total `O(n²/k)`
Worst (clustered)	`O(n²)`	Semua elemen di satu bucket — sort internal dominan
Space	`O(n + k)`	Array `buckets` dengan total `n` elemen
Stable	Ya	Berkat stable sort per bucket

Analisis Expected Time #

Bila input terdistribusi seragam pada [0, 1):

Expected elemen per bucket: n/k.
Sort per bucket (insertion sort): O((n/k)²) expected.
Total sort: k · O((n/k)²) = O(n²/k).
Distribusi dan concatenate: O(n).
Total: O(n + n²/k). Untuk k = n: O(n + n) = O(n).

Stabilitas #

Bucket sort stabil bila sort internal stabil (std::stable_sort atau insertion sort). Elemen equal dalam satu bucket menjaga urutan input. Karena concatenate memproses bucket berurutan, urutan relatif elemen equal lintas-bucket juga terjaga.

Kapan Bucket Sort Cepat #

Bucket sort optimal ketika:

Distribusi seragam — elemen terbagi rata ke bucket.
k ≈ n — setiap bucket berisi rata-rata 1 elemen.
Sort internal efisien — insertion sort untuk bucket kecil.

Kapan Bucket Sort Lambat #

Distribusi ter-cluster — semua elemen jatuh di satu bucket → O(n²).
Range nilai besar — k harus besar untuk resolusi yang baik.
Data non-numerik — perlu fungsi hash untuk distribusi.

Komparasi: Bucket Sort vs `std::sort` #

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

void bucket_sort(std::vector<double>& v) {
    int n = static_cast<int>(v.size());
    if (n < 2) return;
    std::vector<std::vector<double>> buckets(n);
    for (double x : v) {
        int idx = static_cast<int>(n * x);
        if (idx == n) idx = n - 1;
        buckets[idx].push_back(x);
    }
    for (auto& b : buckets) std::stable_sort(b.begin(), b.end());
    int k = 0;
    for (auto& b : buckets) for (double x : b) v[k++] = x;
}

int main() {
    std::mt19937 rng(7);
    std::uniform_real_distribution<double> uni(0.0, 1.0);
    const int N = 100000;
    std::vector<double> a(N), b(N);
    for (int i = 0; i < N; ++i) a[i] = b[i] = uni(rng);

    auto t1 = std::chrono::high_resolution_clock::now();
    bucket_sort(a);
    auto t2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> d_buc = 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 << "Benchmark n=" << N << " (uniform [0,1)):\n";
    std::cout << "  bucket sort : " << d_buc.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):

text
Benchmark n=100000 (uniform [0,1)):
  bucket sort : 15 ms
  std::sort   : 6 ms
  hasil sama  : ya

Bucket sort lebih lambat pada n=100.000 karena overhead alokasi bucket dan push_back elemen satu per satu.
std::sort unggul berkat implementasi introsort yang sangat dioptimasi — akses memori cache-friendly, branch predictor prediktif.
Bucket sort bisa lebih cepat untuk n sangat besar (jutaan elemen) atau bila kita mengganti sort internal dengan insertion sort untuk bucket kecil.

Variasi: Bucket Sort untuk Integer #

Untuk integer dengan rentang [0, k) dan k ≤ n, gunakan k bucket — bucket i menampung elemen bernilai i. Implementasi menjadi sederhana dan kompleksitas O(n + k), mirip counting sort tetapi tanpa cumulative step.

cpp
void bucket_sort_int(std::vector<int>& v, int k) {
    std::vector<std::vector<int>> buckets(k);
    for (int x : v) buckets[x].push_back(x);
    int idx = 0;
    for (auto& b : buckets) for (int x : b) v[idx++] = x;
}

buckets[x]: elemen x langsung ke bucket x. Tidak perlu perhitungan indeks.
Tidak perlu sort internal: setiap bucket hanya berisi elemen dengan nilai identik — sudah terurut.
Efektif untuk rentang nilai kecil. Mirip counting sort tetapi menyimpan elemen lengkap (tidak hanya frekuensi).

Aplikasi #

Mengurutkan nilai floating point [0, 1) — kasus klasik.
Mengurutkan IPK [0.0, 4.0] — rentang kecil, dapat dikonversi ke int.
Sub-rutin hybrid sort — Proxmap sort, flash sort.
Mengurutkan data ter-cluster — kelompokkan dulu, sort tiap kelompok.

Ringkasan #

Bucket sort membagi elemen ke k bucket, mengurutkan tiap bucket, lalu menggabungkan.
Expected O(n + k) pada distribusi seragam; worst case O(n²) pada distribusi ter-cluster.
Stabil bila sort internal stabil.
Tidak in-place — O(n + k) memori tambahan.
Pada praktik, jarang mengalahkan std::sort untuk data acak umum, namun unggul untuk distribusi spesifik yang diketahui seragam.

Pada chapter berikutnya kita akan membahas konsep stabilitas sorting secara mendalam: definisi formal, algoritma mana yang stabil, dan mengapa stabilitas penting untuk multi-key sorting.