Proyek: Benchmark Algoritma Sorting

Setelah mempelajari enam algoritma sorting di Section sebelumnya, pertanyaan praktis muncul: algoritma mana yang paling cepat untuk data tertentu? Big-O menjelaskan tren asimptotik, tetapi konstanta tersembunyi, cache behavior, dan ukuran input kecil sering membalikkan prediksi teoretis. Pada proyek ini kita membangun harness benchmark yang mengukur waktu eksekusi enam algoritma sorting pada beberapa pola data, lalu mencetak tabel perbandingan.

Tool yang akan kita bangun mengukur:

• enam algoritma: bubble sort, insertion sort, merge sort, quick sort, heap sort, dan std::sort STL,
• empat pola data: acak, terurut menaik, terurut menurun, dan hampir terurut,
• tiga ukuran: 1.000, 10.000, dan 100.000 elemen,
• satu metrik: waktu eksekusi dalam milidetik (dengan std::chrono).

Tampilan Akhir Tool #

Berikut contoh output untuk satu ukuran data dengan empat pola:

Benchmark sorting — N = 10000

Algorithm      | random    | sorted    | reversed  | nearly
---------------+-----------+-----------+-----------+-----------
bubble         | 312.4 ms  | 0.0 ms    | 624.1 ms  | 31.0 ms
insertion      |  78.2 ms  | 0.0 ms    | 156.4 ms  |  7.8 ms
merge          |   2.1 ms  |   1.9 ms  |   2.0 ms  |  2.0 ms
quick          |   1.8 ms  |  23.5 ms  |  24.1 ms  |  1.5 ms
heap           |   3.2 ms  |   3.1 ms  |   3.3 ms  |  3.2 ms
std::sort      |   1.2 ms  |   0.4 ms  |   0.5 ms  |  0.4 ms

Tabel ini sekaligus mengonfirmasi teori dan menyingkap kejutan: std::sort memenangkan semua kategori, quick sort jadi sangat lambat pada data terurut (kasus worst-case pivot naive), dan bubble sort tetap jadi yang paling lambat kecuali pada input trivial.

Tujuan Pembelajaran #

Setelah menyelesaikan proyek ini, kita mampu:

• merancang antarmuka seragam void sort(vector<int>&) agar semua algoritma dapat dipanggil dengan kode harness yang sama,
• mengukur waktu eksekusi dengan std::chrono::high_resolution_clock,
• membangkitkan dataset dengan pola berbeda (random, sorted, reversed, nearly sorted),
• memvalidasi hasil sorting dengan assertion agar bug algoritma tidak diam-diam menghasilkan data salah,
• memformat tabel output yang rapi menggunakan std::ostringstream dan std::setw.

Prasyarat #

Proyek ini memanfaatkan materi yang sudah dibahas pada Section sebelumnya:

• Bubble Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort — algoritma yang diuji,
• STL Containers — std::vector, std::priority_queue,
• Recursion — merge sort dan quick sort,
• Time Complexity — konteks teoretis untuk menafsirkan hasil,
• Standard Library Algorithms — std::sort, std::is_sorted, std::shuffle.

Tahapan Pengerjaan #

Proyek dikerjakan dalam empat bagian berurutan:

1. Bagian 1: Perancangan Benchmark — menentukan algoritma, dataset, metrik, dan kontrak antarmuka.
2. Bagian 2: Implementasi Algoritma — menulis enam fungsi sort dengan tanda tangan seragam.
3. Bagian 3: Pengukuran Performa — mengukur waktu dengan std::chrono dan menjalankan seluruh kombinasi.
4. Bagian 4: Analisis Hasil — mencetak tabel perbandingan dan membahas temuan.

Mulailah dari Bagian 1 dan kerjakan secara berurutan. Setiap bagian membangun di atas berkas bagian sebelumnya.