Algoritma yang tampak hebat pada satu dataset bisa kehilangan wajah pada dataset lain, sehingga perbandingan hanya berarti bila semua pesertanya menerima data yang persis sama. Kebutuhan kita pada proyek ini punya dua sisi yang tampak bertentangan: data harus cukup tak teratur urutannya seperti data nyata, tetapi harus identik di setiap eksekusi dan setiap mesin supaya bisa dijadikan bahan pengujian. Dua kebutuhan itu bertemu di satu titik: generator angka semu (pseudo-random number generator) dengan seed tetap. Pada bagian pertama ini kita membangun fondasi itu dan membuktikan sifatnya dengan program kecil yang benar-benar dijalankan.

Mengapa Seed Tetap Mengubah Segalanya #

Generator semu tidak benar-benar mengacak apa pun: ia menghitung deret angka yang tampak berantakan tetapi sepenuhnya ditentukan oleh nilai awal yang disebut seed. Beri dua generator std::mt19937 seed yang sama, dan keduanya akan mengeluarkan deret yang sama persis selamanya. Properti inilah yang kita beli:

  • Reproduksibel: unit test bisa memegang nilai emas (“dataset ke-251 harus bernilai 520”) karena deretnya tetap.
  • Adil: empat algoritma menerima salinan dataset yang sama byte demi byte, sehingga selisih penghitung benar-benar berasal dari algoritmanya.
  • Portabel: standar C++ menetapkan algoritma Mersenne Twister secara persis, jadi std::mt19937 dengan seed 42 menghasilkan deret yang sama di GCC, Clang, maupun MSVC — berbeda dari rand() yang algoritmanya tidak dispesifikasi dan boleh berbeda antar implementasi.

Fungsi buatDataset pada src/cari-urut.cpp #

Seluruh dataset proyek ditumbuhkan oleh satu fungsi pendek di program final:

cpp src/cari-urut.cpp — buatDataset 
// ---------- Dataset deterministik ----------
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;
}

Bedah keputusannya:

  1. std::mt19937 gen(seed);: engine dikonstruksi bersama seed-nya. Dari baris ini, seluruh state generator sudah tertentu — tidak ada sisa pengaruh dari eksekusi lain.
  2. std::uniform_int_distribution<int> dist(0, 1'000'000);: pemetaan output engine ke rentang bilangan bulat 0 sampai 1.000.000 (dua batas inklusif). Pemisah digit ' pada 1'000'000 hanya gaya penulisan agar angka terbaca.
  3. data.reserve(n);: menyediakan kapasitas sekali jalan supaya push_back tidak memicu realokasi berulang — kebiasaan yang sama dengan jadwal kedatangan pada proyek antrean.
  4. dist(gen) per elemen: setiap pemanggilan melangkahkan state engine satu kali. Urutan pemanggilan menentukan isi dataset; karena urutannya tetap, isinya pun tetap.

Properti menarik yang langsung terlihat dari konstruksi ini: dataset berukuran 10 dan dataset berukuran 100.000 yang ditumbuhkan dari seed yang sama akan memiliki delapan nilai pertama yang identik. Deret engine adalah aliran; meminta sepuluh angka atau seratus ribu angka hanya memotong aliran yang sama di titik berbeda.

Membuktikan Determinisme dengan Program Kecil #

Sebelum dipakai menimbang algoritma, kita uji dulu generatornya. Program berikut menumbuhkan dataset yang sama dua kali, mengganti seed, lalu mengambil ringkasan dataset besar:

cpp generator-data.cpp — program lengkap untuk bagian ini 
// generator-data.cpp — Bagian 1: menyiapkan dataset dengan generator berseed tetap.
// std::mt19937 dengan seed 42 menghasilkan deret angka yang PERSIS sama
// pada setiap eksekusi, sehingga dataset "acak" kita tetap deterministik
// dan bisa dijadikan bahan pembanding yang adil antar algoritma.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>

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;
}

void cetakDataset(const std::vector<int>& data, std::size_t banyak) {
    for (std::size_t i = 0; i < banyak && i < data.size(); ++i) {
        std::cout << ' ' << std::setw(7) << data[i];
    }
    std::cout << '\n';
}

int main() {
    std::cout << "Generator dataset mt19937 — seed tetap 42\n";

    std::cout << "\nn=10, seed=42 (eksekusi pertama):";
    cetakDataset(buatDataset(10, 42), 10);

    std::cout << "n=10, seed=42 (eksekusi kedua)  :";
    cetakDataset(buatDataset(10, 42), 10);

    std::cout << "n=10, seed=43 (seed berbeda)    :";
    cetakDataset(buatDataset(10, 43), 10);

    std::vector<int> besar = buatDataset(1000, 42);
    auto posisiMin = std::min_element(besar.begin(), besar.end());
    auto posisiMaks = std::max_element(besar.begin(), besar.end());
    std::cout << "\nn=1000, seed=42, 8 nilai pertama:";
    cetakDataset(besar, 8);
    std::cout << "minimum " << *posisiMin << " pada indeks "
              << (posisiMin - besar.begin()) << ", maksimum " << *posisiMaks
              << " pada indeks " << (posisiMaks - besar.begin()) << '\n';
    return 0;
}
bash 
g++ -std=c++23 -Wall -Wextra generator-data.cpp -o generator-data
./generator-data

Output yang Dihasilkan:

text 
Generator dataset mt19937 — seed tetap 42

n=10, seed=42 (eksekusi pertama):  374540  796543  950715  183434  731994  779691  598659  596850  156018  445833
n=10, seed=42 (eksekusi kedua)  :  374540  796543  950715  183434  731994  779691  598659  596850  156018  445833
n=10, seed=43 (seed berbeda)    :  115054  496861  609067  102914  133391  148772  240589  172132  327139  811037

n=1000, seed=42, 8 nilai pertama:  374540  796543  950715  183434  731994  779691  598659  596850
minimum 520 pada indeks 251, maksimum 997741 pada indeks 289

Tiga hal dari output itu layak digarisbawahi. Pertama, eksekusi pertama dan kedua dengan seed 42 menghasilkan deret yang sama persis — determinisme yang kita cari. Kedua, seed 43 menghasilkan deret yang sama sekali berbeda, bukti bahwa isi dataset benar-benar dikendalikan oleh seed. Ketiga, delapan nilai pertama untuk n=10 dan n=1000 identik — persis properti potongan aliran yang dibahas di atas. Ringkasan akhirnya juga memperkenalkan dua alat standar library yang dipakai program final: std::min_element dan std::max_element, yang keduanya mengembalikan iterator sehingga indeksnya bisa didapat dengan pengurangan pointer (posisiMin - besar.begin()).

Data sudah siap dan sifatnya sudah terbukti. Bagian 2 membangun empat algoritma yang akan memakannya.

Rujukan resmi: std::mt19937 (cppreference) , std::uniform_int_distribution (cppreference) .