Benchmark yang baik bukan sekadar “jalankan sort dan catat waktunya”. Tanpa perancangan, hasil yang diperoleh bisa menyesatkan: algoritma yang menang pada satu dataset bisa kalah telak pada dataset lain. Pada bagian ini kita memilih algoritma yang akan diuji, menentukan pola dataset, menetapkan metrik, dan menyusun kontrak antarmuka agar kode pada Bagian 2 dan 3 dapat tumbuh konsisten.
Algoritma yang Diuji #
Kita akan menguji enam algoritma sorting yang sudah dibahas pada Section Sorting Algorithms:
| Algoritma | Best Case | Average | Worst Case | Stable? | In-place? |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | Ya | Ya |
| Insertion | O(n) | O(n²) | O(n²) | Ya | Ya |
| Merge | O(n log n) | O(n log n) | O(n log n) | Ya | Tidak |
| Quick | O(n log n) | O(n log n) | O(n²) | Tidak | Ya |
| Heap | O(n log n) | O(n log n) | O(n log n) | Tidak | Ya |
std::sort | O(n log n) | O(n log n) | O(n log n) | Tidak | Ya |
std::sort dimasukkan sebagai baseline referensi — algoritma STL berbasis introsort (hybrid quicksort + heapsort + insertion sort) yang sudah dioptimalkan bertahun-tahun. Setiap algoritma custom yang kita tulis seharusnya kalah dari std::sort pada sebagian besar kasus.
Pola Dataset #
Empat pola dataset yang akan diuji:
- Random — angka acak uniform 0 hingga N. Mengukur performa rata-rata.
- Sorted — angka sudah terurut menaik. Mengukur best case untuk algoritma adaptif (bubble, insertion,
std::sort) dan worst case naive quicksort (pivot pertama menghasilkan partisi sangat tidak seimbang). - Reversed — angka terurut menurun. Mengukur worst case untuk bubble, insertion, dan naive quicksort.
- Nearly sorted — array random dengan 5% elemen diacak. Mengukur kemampuan adaptif algoritma pada data yang hampir terurut.
Metrik Pengukuran #
Metrik utama adalah wall-clock time dalam milidetik, diukur dengan std::chrono::high_resolution_clock. Pemilihan wall-clock (bukan CPU time) disengaja karena mencakup efek cache, alokasi memori, dan overhead sistem operasi — semuanya relevan untuk pengguna nyata.
Beberapa keputusan desain yang memengaruhi akurasi:
- Salin data sebelum sort: setiap algoritma menerima salinan dataset yang sama. Tanpa ini, algoritma pertama akan mengubah dataset untuk algoritma berikutnya.
- Ulangi pengukuran sebanyak 5 kali, ambil median: varian waktu eksekusi antar run bisa mencapai 10% karena load CPU lain. Median lebih robust terhadap outlier daripada rata-rata.
- Warmup: jalankan satu kali sebelum pengukuran untuk memanaskan cache instruksi.
Kontrak Antarmuka #
Semua algoritma harus memiliki tanda tangan yang sama agar harness dapat memanggilnya seragam:
// Semua fungsi sort menerima vector by reference dan mengurutkan in-place.
void bubbleSort(std::vector<int>& v);
void insertionSort(std::vector<int>& v);
void mergeSort(std::vector<int>& v);
void quickSort(std::vector<int>& v);
void heapSort(std::vector<int>& v);
void stdSort(std::vector<int>& v); // wrapper std::sort
Harness menyimpan algoritma dalam std::vector<std::pair<std::string, SortFn>> agar dapat diiterasi:
using SortFn = void(*)(std::vector<int>&);
std::vector<std::pair<std::string, SortFn>> algorithms = {
{"bubble", bubbleSort},
{"insertion", insertionSort},
{"merge", mergeSort},
{"quick", quickSort},
{"heap", heapSort},
{"std::sort", stdSort},
};Ukuran Input #
Tiga ukuran input yang akan diuji:
| N | Tujuan |
|---|---|
| 1.000 | Mengukur startup overhead dan konstanta algoritma |
| 10.000 | Ukuran menengah — algoritma O(n²) mulai terasa |
| 100.000 | Ukuran besar — O(n²) akan memakan puluhan detik |
Validasi Hasil #
Setiap pengukuran harus diikuti validasi: hasil sort harus benar-benar terurut. Tanpa validasi, bug pada algoritma bisa menghasilkan waktu seolah-olah cepat padahal data tidak terurut sama sekali. Kita pakai std::is_sorted untuk validasi:
if (!std::is_sorted(v.begin(), v.end())) {
std::cerr << "Sort gagal untuk " << name << "\n";
std::abort();
}Ringkasan Bagian 1 #
Kita telah menetapkan: enam algoritma (bubble, insertion, merge, quick, heap, std::sort), empat pola dataset (random, sorted, reversed, nearly), tiga ukuran input (1K, 10K, 100K), dan metrik wall-clock time dengan validasi hasil. Kontrak antarmuka void sort(vector<int>&) memastikan harness pada Bagian 3 dapat memanggil semua algoritma seragam. Pada Bagian 2, kita mengimplementasikan keenam fungsi tersebut.