Perbandingan Algoritma Sorting

Setelah mempelajari 10 algoritma sorting berbeda, kita perlu panduan praktis untuk memilih algoritma yang tepat. Tidak ada algoritma terbaik universal — setiap pilihan melibatkan trade-off antara kompleksitas waktu, memori, stabilitas, sifat in-place, dan kemudahan implementasi. Pada Chapter ini kita akan merangkum seluruh algoritma sorting dalam tabel komprehensif, memberikan rekomendasi kapan menggunakan masing-masing, dan membedah apa yang dipakai STL C++ (std::sort, std::stable_sort). Pada akhir chapter kita akan memiliki decision tree untuk memilih algoritma sorting berdasarkan karakteristik input.

Tabel Komparasi Komprehensif #

Decision Tree: Memilih Algoritma #

Rekomendasi Berdasarkan Skenario #

Skenario 1: Kode Produksi Umum #

Pilihan: std::sort untuk data tidak perlu stabil; std::stable_sort bila stabilitas penting.

std::sort(v.begin(), v.end());         // introsort: quick + heap + insertion
std::stable_sort(v.begin(), v.end());   // merge sort + insertion

Skenario 2: Data Hampir Terurut #

Pilihan: Insertion sort — best case O(n).

void insertion_sort(std::vector<int>& v) {
    for (std::size_t i = 1; i < v.size(); ++i) {
        int key = v[i];
        std::size_t j = i;
        while (j > 0 && v[j - 1] > key) { v[j] = v[j - 1]; --j; }
        v[j] = key;
    }
}

Skenario 3: Bilangan Bulat dengan Rentang Kecil #

Pilihan: Counting sort — O(n + k) yang menjadi O(n) jika k = O(n).

Skenario 4: Bilangan Bulat 32-bit Banyak #

Pilihan: Radix sort basis 256 — 4 pass, sering 2× lebih cepat dari std::sort.

Skenario 5: Multi-Key Sorting #

Pilihan: std::stable_sort per tahap, dari key paling tidak signifikan.

std::sort: Introsort #

std::sort di libstdc++ dan libc++ mengimplementasikan introsort — hybrid tiga algoritma:

1. Quick sort sebagai algoritma utama — cache-friendly, rata-rata tercepat.
2. Heap sort sebagai fallback bila kedalaman rekursi melebihi 2·log₂ n — mencegah worst case O(n²).
3. Insertion sort untuk sub-array ≤ 16 — konstanta kecil, adaptif.

Hasilnya:

• Worst case: O(n log n) (dijamin).
• Average case: O(n log n) dengan konstanta kecil.
• Best case: hampir O(n) bila data hampir terurut (insertion cutoff).
• Space: O(log n) call stack.
• Stable: Tidak.

std::stable_sort: Merge Sort + Insertion Cutoff #

std::stable_sort biasanya mengimplementasikan merge sort dengan insertion sort cutoff untuk sub-array kecil. Beberapa implementasi menggunakan Tim sort (hybrid insertion + merge yang sangat adaptif).

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

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

void print(const std::vector<Item>& v, const std::string& label) {
    std::cout << label << ":\n";
    for (const auto& it : v) std::cout << "  key=" << it.key << " tag=" << it.tag << '\n';
}

int main() {
    std::vector<Item> items = {
        {5, "Budi"}, {3, "Andi"}, {5, "Citra"}, {3, "Dewi"},
        {1, "Eka"}, {5, "Fani"}, {3, "Gita"}, {1, "Hadi"}
    };
    print(items, "Data awal");

    auto a = items;
    std::sort(a.begin(), a.end(),
        [](const Item& x, const Item& y){ return x.key < y.key; });
    print(a, "\nstd::sort (introsort)");

    auto b = items;
    std::stable_sort(b.begin(), b.end(),
        [](const Item& x, const Item& y){ return x.key < y.key; });
    print(b, "\nstd::stable_sort (merge sort)");

    // Benchmark
    std::mt19937 rng(42);
    const int N = 1'000'000;
    std::vector<int> x(N), y(N);
    for (int i = 0; i < N; ++i) x[i] = y[i] = static_cast<int>(rng());

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

    t1 = std::chrono::high_resolution_clock::now();
    std::stable_sort(y.begin(), y.end());
    t2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> d_stable = t2 - t1;

    std::cout << "\nBenchmark n=" << N << " integer acak:\n";
    std::cout << "  std::sort        : " << d_std.count() << " ms\n";
    std::cout << "  std::stable_sort : " << d_stable.count() << " ms\n";
    std::cout << "  hasil sama : " << (x == y ? "ya" : "tidak") << '\n';

    return 0;
}

Output yang Dihasilkan (waktu bervariasi antar mesin):

Data awal:
  key=5 tag=Budi
  key=3 tag=Andi
  key=5 tag=Citra
  key=3 tag=Dewi
  key=1 tag=Eka
  key=5 tag=Fani
  key=3 tag=Gita
  key=1 tag=Hadi

std::sort (introsort):
  key=1 tag=Eka
  key=1 tag=Hadi
  key=3 tag=Andi
  key=3 tag=Dewi
  key=3 tag=Gita
  key=5 tag=Budi
  key=5 tag=Citra
  key=5 tag=Fani

std::stable_sort (merge sort):
  key=1 tag=Eka
  key=1 tag=Hadi
  key=3 tag=Andi
  key=3 tag=Dewi
  key=3 tag=Gita
  key=5 tag=Budi
  key=5 tag=Citra
  key=5 tag=Fani

Benchmark n=1000000 integer acak:
  std::sort        : 69 ms
  std::stable_sort : 78 ms
  hasil sama : ya

Bedah Hasil #

1. Pada 8 elemen, std::sort dan std::stable_sort menghasilkan output identik — kemungkinan karena n kecil, introsort memakai insertion sort yang stabil. Namun ini tidak dijamin oleh standar.
2. Benchmark n = 1.000.000: std::stable_sort hanya ~13% lebih lambat dari std::sort — bukan 2× seperti yang sering diduga.
3. Memori: std::stable_sort membutuhkan O(n) buffer tambahan — 4 MB untuk n = 10^6 integer.
4. Implikasi: bila stabilitas penting, std::stable_sort adalah pilihan terbaik — overhead kecil.

Rekomendasi untuk Kondisi Spesifik #

Memori Sangat Terbatas (Embedded) #

// Heap sort: O(1) memory, O(n log n) worst case
void heap_sort(std::vector<int>& v) {
    int n = static_cast<int>(v.size());
    // ... (lihat chapter heap-sort)
}

Streaming / Online Sorting #

Insertion sort cocok karena elemen dapat disisipkan satu per satu tanpa menunggu seluruh input tersedia.

Data Terurut Sebagian #

Tim sort atau insertion sort — adaptif, O(n) pada data hampir terurut.

Multi-Key Sort dengan Stabilitas #

std::stable_sort per tahap, dari key paling tidak signifikan.

Integer 32-bit Banyak #

Radix sort basis 256 — sering 2× lebih cepat dari std::sort.

String Panjang Sama #

Radix sort MSD — O(d · (n + b)) dengan d = panjang string.

Peringkat Praktis (Berdasarkan Kecepatan Rata-Rata) #

Untuk n = 1.000.000 integer acak 32-bit:

1. Radix sort basis 256 — ~35 ms
2. std::sort (introsort) — ~70 ms
3. std::stable_sort — ~78 ms
4. Heap sort manual — ~150-200 ms (konstanta besar)
5. Merge sort manual — ~80-100 ms (tanpa insertion cutoff)

Aturan Praktis Cepat #

Jebakan Umum #

1. Quick Sort pada Sorted Input #

Quick sort dengan pivot pertama/terakhir pada sorted input → O(n²). Selalu pakai random pivot, median-of-three, atau langsung std::sort.

2. Counting Sort untuk Rentang Besar #

Mengurutkan 10 nilai dengan rentang [0, 10^9] → array count 10^9 mustahil. Selalu cek k sebelum counting sort.

3. Bucket Sort pada Distribusi Tidak Seragam #

Bila semua elemen jatuh di satu bucket → O(n²). Pastikan distribusi seragam atau gunakan algoritma lain.

4. Tidak Stabil untuk Multi-Key #

Menggunakan std::sort (tidak stabil) untuk multi-key sort akan menghasilkan urutan yang salah. Selalu gunakan std::stable_sort.

5. Mengabaikan Cache Locality #

Algoritma dengan akses acak (heap sort) dapat 3-5× lebih lambat daripada algoritma dengan akses sekuensial (merge sort, quick sort) meskipun kompleksitas asimptotik sama.

Ringkasan Section Sorting #

Pada Section 11 ini kita telah mempelajari:

• Konsep sorting: arah, comparator, stabilitas, in-place, kompleksitas.
• Algoritma comparison-based O(n²): bubble, selection, insertion — sederhana, untuk n kecil.
• Algoritma comparison-based O(n log n): merge, quick, heap — untuk n besar.
• Algoritma non-comparison: counting, radix, bucket — O(n) pada kondisi tertentu.
• Properti: stabilitas dan in-place sebagai dimensi penting.
• Pemilihan: tabel komparasi dan decision tree untuk memilih algoritma yang tepat.

Penutup #

Sorting adalah topik yang tampak sederhana namun memiliki kedalaman luar biasa. Tidak ada algoritma terbaik universal — setiap kasus memerlukan pertimbangan trade-off antara waktu, memori, stabilitas, dan kompleksitas implementasi. Dengan pemahaman tentang 10+ algoritma yang telah kita pelajari, Anda kini memiliki perangkat untuk memilih algoritma yang tepat di setiap situasi.

Pada Section berikutnya, kita akan beralih ke topik rekursi dan backtracking — paradigma pemecahan masalah yang melengkapi divide-and-conquer sorting dengan kemampuan eksplorasi ruang solusi secara sistematis.