Stopwatch punya kelemahan yang sering diabaikan: angkanya tidak hanya menjelaskan algoritma, tetapi juga mesin, beban CPU, cache, bahkan flag optimisasi compiler. Menjalankan dua sort sekali lalu membandingkan milidetiknya lebih mirip jajak pendapat daripada pengukuran. Kita memilih jalan yang lebih disiplin: hitung setiap pembandingan yang terjadi. Big-O memberi kita bentuk kurvanya — O(n), O(log n), O(n log n) — dan penghitung memberi angka kurva itu pada data nyata, dengan sifat yang paling kita perlukan sejak bagian 1: sama di setiap eksekusi.

Instrumen: Penghitung yang Diselipkan ke Algoritma #

Seluruh algoritma pada src/cari-urut.cpp berbagi satu struct kecil:

cpp src/cari-urut.cpp — StatistikAlgo 
struct StatistikAlgo {
    long long perbandingan = 0;
    long long pemindahan = 0;
};

Setiap fungsi menerima StatistikAlgo* stat = nullptr dan menambah penghitung hanya bila pointer-nya diisi — if (stat) { ++stat->perbandingan; } di setiap titik pembandingan. Desain ini murah dan tidak mengganggu: pemanggil yang hanya ingin mengurutkan (seperti program uji di bagian 2) memanggil tanpa argumen terakhir dan membayar biaya satu pemeriksaan pointer per perbandingan; pemanggil yang ingin mengukur mengirimkan alamat struct-nya. Penghitungan dilakukan di titik yang konsisten: satu putaran loop pencarian dihitung satu perbandingan, satu keputusan penggabungan merge dihitung satu, satu pemeriksaan data[j] < pivot dihitung satu. Konsistensi definisi inilah yang membuat angka antarkolom layak disandingkan.

Tabel Pencarian: Linear Menyisir, Binary Melompat #

Program berikut menjalankan keempat algoritma bertingkat ukuran — 100, 1.000, 10.000, 100.000 elemen — dengan target yang dipastikan absen sehingga kita mengukur kasus terburuk pencarian:

cpp hitung-perbandingan.cpp — program lengkap untuk bagian ini 
// hitung-perbandingan.cpp — Bagian 3: penghitung perbandingan menjadi tabel.
// Setiap algoritma menerima pointer ke StatistikAlgo; setelah dijalankan,
// isinya dicetak sebagai tabel deterministik — angka yang sama pada
// setiap mesin dan setiap eksekusi, karena hanya menghitung, bukan mengukur.
#include <cmath>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>

struct StatistikAlgo {
    long long perbandingan = 0;
};

template <typename T>
int cariLinear(const std::vector<T>& data, const T& target, StatistikAlgo& stat) {
    for (std::size_t i = 0; i < data.size(); ++i) {
        ++stat.perbandingan;
        if (data[i] == target) {
            return static_cast<int>(i);
        }
    }
    return -1;
}

template <typename T>
int cariBinary(const std::vector<T>& data, const T& target, StatistikAlgo& stat) {
    int kiri = 0;
    int kanan = static_cast<int>(data.size()) - 1;
    while (kiri <= kanan) {
        int tengah = kiri + (kanan - kiri) / 2;
        ++stat.perbandingan; // satu putaran loop = satu pembandingan
        if (data[tengah] == target) {
            return tengah;
        }
        if (data[tengah] < target) {
            kiri = tengah + 1;
        } else {
            kanan = tengah - 1;
        }
    }
    return -1;
}

template <typename T>
void mergeSortRekursif(std::vector<T>& data, std::vector<T>& bantu,
                       std::size_t kiri, std::size_t kanan, StatistikAlgo& stat) {
    if (kanan - kiri < 2) {
        return;
    }
    std::size_t tengah = kiri + (kanan - kiri) / 2;
    mergeSortRekursif(data, bantu, kiri, tengah, stat);
    mergeSortRekursif(data, bantu, tengah, kanan, stat);
    std::size_t i = kiri, j = tengah, k = kiri;
    while (i < tengah && j < kanan) {
        ++stat.perbandingan;
        if (data[j] < data[i]) {
            bantu[k++] = data[j++];
        } else {
            bantu[k++] = data[i++];
        }
    }
    while (i < tengah) bantu[k++] = data[i++];
    while (j < kanan) bantu[k++] = data[j++];
    for (std::size_t x = kiri; x < kanan; ++x) data[x] = bantu[x];
}

template <typename T>
void mergeSort(std::vector<T>& data, StatistikAlgo& stat) {
    std::vector<T> bantu(data.size());
    mergeSortRekursif(data, bantu, 0, data.size(), stat);
}

template <typename T>
int partisi(std::vector<T>& data, int kiri, int kanan, StatistikAlgo& stat) {
    int tengah = kiri + (kanan - kiri) / 2;
    std::swap(data[tengah], data[kanan]);
    T pivot = data[kanan];
    int batas = kiri;
    for (int j = kiri; j < kanan; ++j) {
        ++stat.perbandingan;
        if (data[j] < pivot) {
            std::swap(data[j], data[batas]);
            ++batas;
        }
    }
    std::swap(data[batas], data[kanan]);
    return batas;
}

template <typename T>
void quickSortRekursif(std::vector<T>& data, int kiri, int kanan, StatistikAlgo& stat) {
    if (kiri >= kanan) {
        return;
    }
    int posisiPivot = partisi(data, kiri, kanan, stat);
    quickSortRekursif(data, kiri, posisiPivot - 1, stat);
    quickSortRekursif(data, posisiPivot + 1, kanan, stat);
}

template <typename T>
void quickSort(std::vector<T>& data, StatistikAlgo& stat) {
    if (!data.empty()) {
        quickSortRekursif(data, 0, static_cast<int>(data.size()) - 1, stat);
    }
}

std::vector<int> buatDataset(std::size_t n, unsigned seed) {
    std::mt19937 gen(seed);
    std::uniform_int_distribution<int> dist(0, 1'000'000);
    std::vector<int> data;
    data.reserve(n);
    for (std::size_t i = 0; i < n; ++i) {
        data.push_back(dist(gen));
    }
    return data;
}

std::vector<int> salinanTerurut(std::size_t n) {
    std::vector<int> data = buatDataset(n, 42);
    StatistikAlgo diam; // pengurutan persiapan tidak dihitung
    mergeSort(data, diam);
    return data;
}

int main() {
    std::cout << "Pencarian: target -1 (dipastikan absen), data seed 42\n";
    std::cout << "     n | linear (absen) | binary (absen) | log2 n\n";
    for (std::size_t n : {100uz, 1000uz, 10000uz, 100000uz}) {
        std::vector<int> data = salinanTerurut(n);
        StatistikAlgo lin, bin;
        cariLinear(data, -1, lin);
        cariBinary(data, -1, bin);
        std::cout << std::right << std::setw(6) << n << " |" << std::setw(15)
                  << lin.perbandingan << " |" << std::setw(15)
                  << bin.perbandingan << " |" << std::setw(7) << std::fixed
                  << std::setprecision(1) << std::log2(static_cast<double>(n))
                  << '\n';
    }

    std::cout << "\nPengurutan: data acak seed 42 (kedua algoritma menerima\n";
    std::cout << "salinan data yang sama)\n";
    std::cout << "     n | merge: perbandingan | merge/elemen | quick: perbandingan | quick/elemen\n";
    for (std::size_t n : {100uz, 1000uz, 10000uz, 100000uz}) {
        std::vector<int> dataMerge = buatDataset(n, 42);
        std::vector<int> dataQuick = dataMerge;
        StatistikAlgo statMerge, statQuick;
        mergeSort(dataMerge, statMerge);
        quickSort(dataQuick, statQuick);
        double perElemenMerge =
            static_cast<double>(statMerge.perbandingan) / static_cast<double>(n);
        double perElemenQuick =
            static_cast<double>(statQuick.perbandingan) / static_cast<double>(n);
        std::cout << std::right << std::setw(6) << n << " |" << std::setw(20)
                  << statMerge.perbandingan << " |" << std::setw(13)
                  << std::fixed << std::setprecision(1) << perElemenMerge << " |"
                  << std::setw(20) << statQuick.perbandingan << " |"
                  << std::setw(13) << perElemenQuick << '\n';
    }
    return 0;
}
bash 
g++ -std=c++23 -Wall -Wextra hitung-perbandingan.cpp -o hitung-perbandingan
./hitung-perbandingan

Output yang Dihasilkan:

text 
Pencarian: target -1 (dipastikan absen), data seed 42
     n | linear (absen) | binary (absen) | log2 n
   100 |            100 |              6 |    6.6
  1000 |           1000 |              9 |   10.0
 10000 |          10000 |             13 |   13.3
100000 |         100000 |             16 |   16.6

Pengurutan: data acak seed 42 (kedua algoritma menerima
salinan data yang sama)
     n | merge: perbandingan | merge/elemen | quick: perbandingan | quick/elemen
   100 |                 538 |          5.4 |                 635 |          6.3
  1000 |                8703 |          8.7 |               11031 |         11.0
 10000 |              120459 |         12.0 |              155598 |         15.6
100000 |             1536414 |         15.4 |             1864061 |         18.6

Baca tabel pertama dari kiri ke kanan. Kolom linear (absen) bernilai persis n pada setiap baris — kasus terburuk linear search memang menyisir sampai elemen terakhir — sehingga melipatgandakan ukuran data melipatgandakan pula kerjanya; itulah O(n) dalam angka. Kolom binary (absen) bergerak di lajur yang sama sekali berbeda: 6 → 9 → 13 → 16 sementara n naik seribu kali lipat. Bandingkan dengan kolom log2 n (6.6 → 10.0 → 13.3 → 16.6) dan polanya terlihat: setiap penambahan angka biner pada log2 n dibayar satu perbandingan binary search. Saat data membesar seribu kali, kerja binary search hanya bertambah sekitar tiga kali lipat — selisih inilah yang membuat indeks terurut menjadi standar pada database dan filesystem.

Tabel Pengurutan: n log2 n dalam Angka #

Tabel kedua menimbang merge sort dan quick sort pada data acak yang sama (keduanya menerima salinan dataset seed 42 yang identik, sehingga selisih angka murni berasal dari algoritma). Karena total kerja sorting sebanding n log2 n, kita tambahkan kolom perbandingan per elemen — perbandingan / n — yang seharusnya bergerak seperti log2 n:

  • merge sort per elemen: 5.4 → 8.7 → 12.0 → 15.4, sementara log2 n bergerak 6.6 → 10.0 → 13.3 → 16.6. Per elemen tumbuh pelan seiring logaritma; totalnya n x log2 n tumbuh sebanding dengan tabel — dari 538 perbandingan pada n=100 menjadi 1.536.414 pada n=100.000, hanya sekitar 2.900 kali lipat untuk data yang membesar 1.000 kali lipat.
  • quick sort lebih banyak membandingkan pada data acak ini (11.031 lawan 8.703 pada n=1.000). Pola ini bukan kebetulan: setiap pemanggilan partisi membandingkan setiap elemen dengan pivot sekali, dan analisis rata-rata quick sort memang sekitar 1,39 kali n log2 n.

Apakah quick sort kalah? Tabel program final di bagian 4 melengkapi ceritanya dengan kolom pemindahan: pada n=1.000 quick sort melakukan 4.816 pertukaran berbanding 9.976 salinan merge sort — setengahnya. Quick sort juga bekerja in-place tanpa buffer. Jadi pertukarannya nyata dan terukur: merge sort membeli jaminan O(n log n) dan stabilitas dengan memori serta salinan, quick sort membeli kecepatan dan hemat memori dengan risiko kasus terburuk O(n²) bila pivot buruk.

Dari Tabel ke Notasi Big-O #

Tabel di atas adalah bukti empiris untuk notasi yang dibahas pada chapter big-o-notation:

AlgoritmaPola angka pada tabelKompleksitas
cariLinear (absen)persis nO(n)
cariBinary (absen)sekitar log2 n + 1O(log n)
mergeSortsekitar n log2 nO(n log n), dijamin
quickSortsekitar 1,4 n log2 n rata-rataO(n log n) rata-rata, O(n²) terburuk

Dua catatan menutup bagian ini. Pertama, Big-O menyembunyikan konstanta — tabel kita justru memperlihatkannya: dua algoritma dengan kompleksitas rata-rata sekelas tetap berbeda sekitar 25-30% pada jumlah perbandingan. Kedua, jaminan itu penting: pada dataset dengan pola tertentu quick sort bisa jatuh ke O(n²), dan pilihan pivot tengah yang kita pakai adalah salah satu penangkal sederhananya. Laporan lengkap kedua algoritma pada tiga ukuran dataset menanti di program final.

Rujukan resmi: std::log2 (cppreference) , default arguments (cppreference) .