Implementasi enam algoritma telah siap dan terverifikasi. Sekarang kita membungkusnya dalam harness pengukuran yang menjalankan setiap algoritma pada setiap pola dataset, mengukur wall-clock time dengan std::chrono, dan mengumpulkan hasil ke dalam struktur data yang siap dicetak sebagai tabel. Pada bagian ini fokus adalah pengukuran; pencetakan tabel analisis menyusul pada Bagian 4.
Generator Dataset #
Empat pola dataset yang dibangun dari benih deterministik agar hasil benchmark dapat direproduksi:
cpp
#include <algorithm>
#include <random>
#include <vector>
std::vector<int> generateRandom(int n, unsigned seed) {
std::mt19937 rng(seed);
std::uniform_int_distribution<int> dist(0, n);
std::vector<int> v(n);
for (int i = 0; i < n; ++i) v[i] = dist(rng);
return v;
}
std::vector<int> generateSorted(int n) {
std::vector<int> v(n);
for (int i = 0; i < n; ++i) v[i] = i;
return v;
}
std::vector<int> generateReversed(int n) {
std::vector<int> v(n);
for (int i = 0; i < n; ++i) v[i] = n - i;
return v;
}
std::vector<int> generateNearlySorted(int n, unsigned seed) {
std::vector<int> v = generateSorted(n);
std::mt19937 rng(seed);
int swaps = std::max(1, n / 20); // 5% elemen diacak
for (int s = 0; s < swaps; ++s) {
int i = rng() % n, j = rng() % n;
std::swap(v[i], v[j]);
}
return v;
}Fungsi Pengukuran #
Pengukuran memakai std::chrono::high_resolution_clock. Setiap algoritma dijalankan 5 kali, median diambil. Sebelum pengukuran, dataset disalin agar input setiap algoritma identik.
cpp
#include <chrono>
double measureOnce(void(*fn)(std::vector<int>&), const std::vector<int>& input) {
std::vector<int> v = input; // salin agar input tidak berubah
auto t0 = std::chrono::high_resolution_clock::now();
fn(v);
auto t1 = std::chrono::high_resolution_clock::now();
if (!std::is_sorted(v.begin(), v.end())) {
std::cerr << "Sort gagal validasi\n";
std::abort();
}
return std::chrono::duration<double, std::milli>(t1 - t0).count();
}
double measureMedian(void(*fn)(std::vector<int>&),
const std::vector<int>& input, int runs = 5) {
std::vector<double> times;
times.reserve(runs);
for (int r = 0; r < runs; ++r) times.push_back(measureOnce(fn, input));
std::sort(times.begin(), times.end());
return times[runs / 2];
}Program Lengkap Bagian 3 #
Berikut program yang menggabungkan keenam algoritma (dari Bagian 2), generator dataset, dan fungsi pengukuran. Output berupa raw waktu per kombinasi algoritma × pola.
cpp
#include <algorithm>
#include <cassert>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
// (definisi bubbleSort, insertionSort, mergeSort, quickSort,
// heapSort, stdSort dari Bagian 2 — disertakan di sini)
void bubbleSort(std::vector<int>& v) {
int n = (int)v.size();
for (int i = 0; i < n - 1; ++i) {
bool swapped = false;
for (int j = 0; j < n - 1 - i; ++j) {
if (v[j] > v[j + 1]) { std::swap(v[j], v[j + 1]); swapped = true; }
}
if (!swapped) break;
}
}
void insertionSort(std::vector<int>& v) {
for (size_t i = 1; i < v.size(); ++i) {
int key = v[i]; int j = (int)i - 1;
while (j >= 0 && v[j] > key) { v[j + 1] = v[j]; --j; }
v[j + 1] = key;
}
}
static void mergeRec(std::vector<int>& v, std::vector<int>& buf, size_t lo, size_t hi) {
if (hi - lo <= 1) return;
size_t mid = lo + (hi - lo) / 2;
mergeRec(v, buf, lo, mid); mergeRec(v, buf, mid, hi);
size_t i = lo, j = mid, k = lo;
while (i < mid && j < hi) v[i] <= v[j] ? buf[k++] = v[i++] : buf[k++] = v[j++];
while (i < mid) buf[k++] = v[i++];
while (j < hi) buf[k++] = v[j++];
for (size_t p = lo; p < hi; ++p) v[p] = buf[p];
}
void mergeSort(std::vector<int>& v) {
if (v.size() < 2) return;
std::vector<int> buf(v.size()); mergeRec(v, buf, 0, v.size());
}
static int partition(std::vector<int>& v, int lo, int hi) {
int pivot = v[hi]; int i = lo - 1;
for (int j = lo; j < hi; ++j) if (v[j] <= pivot) std::swap(v[++i], v[j]);
std::swap(v[i + 1], v[hi]); return i + 1;
}
static void quickRec(std::vector<int>& v, int lo, int hi) {
if (lo >= hi) return;
int p = partition(v, lo, hi); quickRec(v, lo, p - 1); quickRec(v, p + 1, hi);
}
void quickSort(std::vector<int>& v) {
if (v.size() < 2) return;
quickRec(v, 0, (int)v.size() - 1);
}
static void heapify(std::vector<int>& v, int n, int i) {
int largest = i, l = 2*i+1, r = 2*i+2;
if (l < n && v[l] > v[largest]) largest = l;
if (r < n && v[r] > v[largest]) largest = r;
if (largest != i) { std::swap(v[i], v[largest]); heapify(v, n, largest); }
}
void heapSort(std::vector<int>& v) {
int n = (int)v.size();
for (int i = n/2 - 1; i >= 0; --i) heapify(v, n, i);
for (int i = n - 1; i > 0; --i) { std::swap(v[0], v[i]); heapify(v, i, 0); }
}
void stdSort(std::vector<int>& v) { std::sort(v.begin(), v.end()); }
std::vector<int> generateRandom(int n, unsigned seed) {
std::mt19937 rng(seed); std::uniform_int_distribution<int> dist(0, n);
std::vector<int> v(n); for (int i = 0; i < n; ++i) v[i] = dist(rng); return v;
}
std::vector<int> generateSorted(int n) {
std::vector<int> v(n); for (int i = 0; i < n; ++i) v[i] = i; return v;
}
std::vector<int> generateReversed(int n) {
std::vector<int> v(n); for (int i = 0; i < n; ++i) v[i] = n - i; return v;
}
std::vector<int> generateNearlySorted(int n, unsigned seed) {
std::vector<int> v = generateSorted(n);
std::mt19937 rng(seed); int swaps = std::max(1, n / 20);
for (int s = 0; s < swaps; ++s) std::swap(v[rng()%n], v[rng()%n]);
return v;
}
double measureMedian(void(*fn)(std::vector<int>&),
const std::vector<int>& input, int runs = 5) {
std::vector<double> times;
for (int r = 0; r < runs; ++r) {
std::vector<int> v = input;
auto t0 = std::chrono::high_resolution_clock::now();
fn(v);
auto t1 = std::chrono::high_resolution_clock::now();
assert(std::is_sorted(v.begin(), v.end()));
times.push_back(std::chrono::duration<double, std::milli>(t1 - t0).count());
}
std::sort(times.begin(), times.end());
return times[runs / 2];
}
int main() {
using SortFn = void(*)(std::vector<int>&);
std::vector<std::pair<std::string, SortFn>> algos = {
{"bubble", bubbleSort}, {"insertion", insertionSort},
{"merge", mergeSort}, {"quick", quickSort},
{"heap", heapSort}, {"std::sort", stdSort},
};
int N = 10000;
unsigned seed = 42;
std::vector<std::pair<std::string, std::vector<int>>> datasets = {
{"random", generateRandom(N, seed)},
{"sorted", generateSorted(N)},
{"reversed",generateReversed(N)},
{"nearly", generateNearlySorted(N, seed)},
};
std::cout << "Benchmark N=" << N << " (median of 5 runs, in ms)\n";
for (auto& algo : algos) {
std::cout << algo.first << ":";
for (auto& ds : datasets) {
double ms = measureMedian(algo.second, ds.second);
std::cout << " " << ds.first << "=" << ms;
}
std::cout << "\n";
}
return 0;
}Output yang Dihasilkan:
text
Benchmark N=10000 (median of 5 runs, in ms)
bubble: random=162.172 sorted=0.006 reversed=295.301 nearly=48.032
insertion: random=8.329 sorted=0.008 reversed=16.498 nearly=1.119
merge: random=0.628 sorted=0.173 reversed=0.172 nearly=0.244
quick: random=0.493 sorted=25.709 reversed=20.368 nearly=0.407
heap: random=0.758 sorted=0.456 reversed=0.510 nearly=0.512
std::sort: random=0.455 sorted=0.053 reversed=0.043 nearly=0.122Bedah Baris Penting #
std::vector<int> v = input: salinan dibuat untuk setiap run agar input tidak termodifikasi. Tanpa ini, algoritma pertama akan mengurutkan input untuk algoritma kedua — pengukuran tidak valid.std::mt19937 rng(seed): generator acak deterministik. Seed yang sama menghasilkan dataset yang sama, sehingga benchmark dapat direproduksi lintas mesin.assert(std::is_sorted(...)): validasi pasca-sort. Bila algoritma salah menghasilkan output tidak terurut, program crash seketika — tidak ada data benchmark yang menyesatkan.times[runs / 2]: indeks tengah dari array terurut adalah median. Median dipilih alih-alih rata-rata karena lebih tahan terhadap outlier (misalnya OS mengambil CPU untuk tugas lain selama satu run).std::chrono::duration<double, std::milli>(t1 - t0).count(): konversi durasi ke millidetik dengan presisi floating-point.doubledipilih agar presisi mikrodetik tidak hilang pada pengukuran singkat.
Kompilasi dan Pengujian #
bash
g++ -std=c++17 -O2 -Wall -Wextra -o measure.bin measure.cpp
./measure.binPada Bagian 4 kita memformat hasil ini menjadi tabel yang rapi dan membahas temuan yang muncul.