Proyek: Sistem Pencarian dan Pengurutan

Setelah simulasi antrean yang berjalan di atas jadwal tetap, proyek ini menambahkan satu bumbu baru pada resep deterministik: data “acak” yang ditanam dengan seed tetap. Kita membangun alat pembanding algoritma — linear search melawan binary search, merge sort melawan quick sort — lalu menilai harganya bukan dengan stopwatch, melainkan dengan penghitung perbandingan yang angkanya persis sama di setiap mesin dan setiap eksekusi. Hasil akhirnya adalah laporan tabel yang bisa dijadikan nilai emas pada unit test, bukan deretan milidetik yang berubah-ubah.

Pencarian dan pengurutan dipilih karena keduanya fondasi dari hampir semua sistem data: daftar produk yang disortir sebelum ditampilkan, indeks yang dicari dengan binary search, dataset yang dipartisi sebelum diolah. Keempat algoritmanya kita tulis manual — bukan memanggil std::sort — karena tujuan proyek adalah melihat mekanisme di balik layar dan memasang instrumen penghitung tepat di titik pembandingan. Adil pun terjaga: setiap algoritma menerima dataset yang persis sama, ditumbuhkan dari seed yang sama.

Kita membangunnya dalam empat bagian:

1. Bagian 1: Menyiapkan Data — generator dataset std::mt19937 berseed tetap dan bukti bahwa “acak” pun bisa deterministik.
2. Bagian 2: Mengimplementasikan Algoritma — linear/binary search serta merge/quick sort versi manual kita, dengan alasan di balik setiap keputusan.
3. Bagian 3: Membandingkan Kompleksitas — penghitung perbandingan yang diubah menjadi tabel pertumbuhan O(n), O(log n), dan O(n log n).
4. Bagian 4: Mengukur Performa — program final, catatan hati-hati tentang pengukuran waktu, dan harness uji 42 pemeriksaan.

Perilaku yang Diharapkan #

Program final menyaring tiga ukuran dataset (1.000, 10.000, dan 100.000 elemen) dan melaporkan ringkasan dataset, hasil pencarian pada data terurut, serta hasil pengurutan kedua algoritma pada data acak yang sama:

g++ -std=c++23 -Wall -Wextra cari-urut-final.cpp -o cari-urut
./cari-urut

Output yang Dihasilkan (potongan):

Pencarian pada data terurut (target = nilai indeks tengah; target absen = -1):
       n |  posisi linear | linear (ada) |  posisi binary | binary (ada) | linear (absen) | binary (absen)
    1000 |           500 |          501 |           500 |            9 |           1000 |              9
   10000 |          5000 |         5001 |          5000 |           13 |          10000 |             13
  100000 |         50000 |        50001 |         50000 |           16 |         100000 |             16

Pengurutan data acak yang sama pada kedua algoritma:
       n | merge: perbandingan | merge: salinan | quick: perbandingan | quick: pertukaran | terurut
    1000 |               8703 |           9976 |               11031 |               4816 |     ya
   10000 |             120459 |         133616 |              155598 |              70293 |     ya
  100000 |            1536414 |        1668928 |             1864061 |             938314 |     ya

Dua pola di tabel itu adalah inti proyek. Kolom binary (absen) hanya naik 9 → 13 → 16 sementara ukuran data naik seratus kali lipat — itulah wajah O(log n) — dan kedua algoritma pengurutan menghasilkan urutan yang sama dengan jumlah kerja yang berbeda polanya.

Seluruh kode sumber final tersedia pada bagian Berkas Sumber (src/cari-urut.cpp) beserta harness uji (tests/uji-cari-urut.cpp) yang memeriksa kebenaran pencarian, kesetaraan dengan std::sort, nilai emas penghitung, dan stabilitas merge sort. Mari kita mulai dari bahan bakunya: data.