Semua bahan sudah di meja: dataset deterministik dari bagian 1, empat algoritma yang terbukti benar dari bagian 2, dan penghitung perbandingan dari bagian 3. Bagian terakhir merakit semuanya menjadi program final yang mencetak laporan utuh, membahas cara mengukur waktu eksekusi beserta batas-batasnya pada VM kursus ini, lalu mengunci seluruh perilaku dengan harness uji. Inilah bagian yang mengubah kumpulan fungsi menjadi alat yang bisa dikutip.
Program Final: Laporan yang Bisa Direproduksi #
cari-urut-final.cpp — salinan utuh dari src/cari-urut.cpp — menjalankan tiga ukuran dataset dan mencetak tiga laporan berturut-turut:
cpp
// cari-urut.cpp — Proyek: Sistem Pencarian dan Pengurutan (versi final).
// Alat pembanding algoritma: linear/binary search serta merge/quick sort
// yang diimplementasikan manual, diuji pada dataset acak DETERMINISTIK
// (mt19937 seed 42). Keluaran hanya berisi hasil penghitungan perbandingan,
// sehingga setiap eksekusi pada data yang sama menghasilkan angka yang sama.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>
struct StatistikAlgo {
long long perbandingan = 0;
long long pemindahan = 0;
};
// ---------- 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;
}
template <typename T>
bool sudahTerurut(const std::vector<T>& data) {
for (std::size_t i = 1; i < data.size(); ++i) {
if (data[i - 1] > data[i]) {
return false;
}
}
return true;
}
// ---------- Pencarian ----------
template <typename T>
int cariLinear(const std::vector<T>& data, const T& target,
StatistikAlgo* stat = nullptr) {
for (std::size_t i = 0; i < data.size(); ++i) {
if (stat) {
++stat->perbandingan;
}
if (data[i] == target) {
return static_cast<int>(i);
}
}
return -1;
}
template <typename T>
int cariBinary(const std::vector<T>& data, const T& target,
StatistikAlgo* stat = nullptr) {
int kiri = 0;
int kanan = static_cast<int>(data.size()) - 1;
while (kiri <= kanan) {
int tengah = kiri + (kanan - kiri) / 2;
if (stat) {
++stat->perbandingan; // satu putaran = satu pembandingan
}
if (data[tengah] == target) {
return tengah;
}
if (data[tengah] < target) {
kiri = tengah + 1;
} else {
kanan = tengah - 1;
}
}
return -1;
}
// ---------- Pengurutan: merge sort ----------
template <typename T>
void mergeSortRekursif(std::vector<T>& data, std::vector<T>& bantu,
std::size_t kiri, std::size_t kanan,
StatistikAlgo* stat) {
if (kanan - kiri < 2) {
return; // 0 atau 1 elemen dianggap sudah terurut
}
std::size_t tengah = kiri + (kanan - kiri) / 2;
mergeSortRekursif(data, bantu, kiri, tengah, stat);
mergeSortRekursif(data, bantu, tengah, kanan, stat);
// Gabungkan [kiri, tengah) dan [tengah, kanan) menjadi satu rentang urut.
std::size_t i = kiri;
std::size_t j = tengah;
std::size_t k = kiri;
while (i < tengah && j < kanan) {
if (stat) {
++stat->perbandingan;
}
if (data[j] < data[i]) {
bantu[k++] = data[j++];
if (stat) ++stat->pemindahan;
} else {
bantu[k++] = data[i++]; // ambil kiri dulu agar stabil
if (stat) ++stat->pemindahan;
}
}
while (i < tengah) {
bantu[k++] = data[i++];
if (stat) ++stat->pemindahan;
}
while (j < kanan) {
bantu[k++] = data[j++];
if (stat) ++stat->pemindahan;
}
for (std::size_t x = kiri; x < kanan; ++x) {
data[x] = bantu[x]; // salin hasil penggabungan kembali
}
}
template <typename T>
void mergeSort(std::vector<T>& data, StatistikAlgo* stat = nullptr) {
std::vector<T> bantu(data.size());
mergeSortRekursif(data, bantu, 0, data.size(), stat);
}
// ---------- Pengurutan: quick sort ----------
template <typename T>
int partisi(std::vector<T>& data, int kiri, int kanan, StatistikAlgo* stat) {
int tengah = kiri + (kanan - kiri) / 2;
std::swap(data[tengah], data[kanan]); // pivot dipindah ke ujung kanan
T pivot = data[kanan];
int batas = kiri;
for (int j = kiri; j < kanan; ++j) {
if (stat) {
++stat->perbandingan;
}
if (data[j] < pivot) {
std::swap(data[j], data[batas]);
++batas;
if (stat) ++stat->pemindahan;
}
}
std::swap(data[batas], data[kanan]); // pivot ke posisi akhirnya
return batas;
}
template <typename T>
void quickSortRekursif(std::vector<T>& data, int kiri, int kanan,
StatistikAlgo* stat) {
if (kiri >= kanan) {
return;
}
int posisiPivot = partisi(data, kiri, kanan, stat);
quickSortRekursif(data, kiri, posisiPivot - 1, stat);
quickSortRekursif(data, posisiPivot + 1, kanan, stat);
}
template <typename T>
void quickSort(std::vector<T>& data, StatistikAlgo* stat = nullptr) {
if (data.empty()) {
return;
}
quickSortRekursif(data, 0, static_cast<int>(data.size()) - 1, stat);
}
// ---------- Laporan ----------
void cetakPencarian(const std::vector<int>& terurut) {
int target = terurut[terurut.size() / 2]; // nilai pada indeks tengah
StatistikAlgo linAda, binAda, linAbsen, binAbsen;
int posisiLin = cariLinear(terurut, target, &linAda);
int posisiBin = cariBinary(terurut, target, &binAda);
cariLinear(terurut, -1, &linAbsen); // -1 dijamin tidak ada pada data
cariBinary(terurut, -1, &binAbsen);
std::cout << std::right << std::setw(8) << terurut.size() << " |"
<< std::setw(14) << posisiLin << " |" << std::setw(13)
<< linAda.perbandingan << " |" << std::setw(14) << posisiBin
<< " |" << std::setw(13) << binAda.perbandingan << " |"
<< std::setw(15) << linAbsen.perbandingan << " |" << std::setw(15)
<< binAbsen.perbandingan << '\n';
}
void cetakPengurutan(std::size_t n) {
std::vector<int> dataA = buatDataset(n, 42);
std::vector<int> dataB = dataA; // quick sort menerima salinan yang sama
StatistikAlgo statMerge;
mergeSort(dataA, &statMerge);
StatistikAlgo statQuick;
quickSort(dataB, &statQuick);
bool duaDuanyaUrut = sudahTerurut(dataA) && dataA == dataB;
std::cout << std::right << std::setw(8) << n << " |" << std::setw(19)
<< statMerge.perbandingan << " |" << std::setw(15)
<< statMerge.pemindahan << " |" << std::setw(20)
<< statQuick.perbandingan << " |" << std::setw(19)
<< statQuick.pemindahan << " |" << std::setw(7)
<< (duaDuanyaUrut ? "ya" : "TIDAK") << '\n';
}
int main() {
std::cout << "Sistem Pencarian dan Pengurutan — dataset mt19937 seed 42\n";
std::cout << "\nRingkasan dataset (8 nilai pertama, minimum, maksimum):\n";
for (std::size_t n : {1000uz, 10000uz, 100000uz}) {
std::vector<int> data = buatDataset(n, 42);
std::cout << " n=" << std::setw(6) << std::left << n << std::right
<< " pertama:";
for (std::size_t i = 0; i < 8; ++i) {
std::cout << ' ' << std::setw(7) << data[i];
}
std::cout << " min " << *std::min_element(data.begin(), data.end())
<< " maks " << *std::max_element(data.begin(), data.end())
<< '\n';
}
std::cout << "\nPencarian pada data terurut (target = nilai indeks tengah; "
"target absen = -1):\n";
std::cout << " n | posisi linear | linear (ada) | posisi binary |"
" binary (ada) | linear (absen) | binary (absen)\n";
for (std::size_t n : {1000uz, 10000uz, 100000uz}) {
std::vector<int> salinan = buatDataset(n, 42);
mergeSort(salinan);
cetakPencarian(salinan);
}
std::cout << "\nPengurutan data acak yang sama pada kedua algoritma:\n";
std::cout << " n | merge: perbandingan | merge: salinan |"
" quick: perbandingan | quick: pertukaran | terurut\n";
for (std::size_t n : {1000uz, 10000uz, 100000uz}) {
cetakPengurutan(n);
}
std::cout << "\nKesimpulan:\n";
std::cout << "- cariLinear tumbuh sebanding n; cariBinary hanya ~log2 n\n";
std::cout << " (lihat kolom binary (absen): hanya naik 9 -> 13 -> 16\n";
std::cout << " saat n naik 1000 -> 10000 -> 100000).\n";
std::cout << "- Kedua algoritma pengurutan tumbuh sekitar n log2 n dan\n";
std::cout << " menghasilkan urutan yang sama; quick sort rata-rata lebih\n";
std::cout << " sedikit melakukan perbandingan pada data acak ini.\n";
std::cout << "- Seluruh angka adalah hasil penghitungan, bukan pengukuran\n";
std::cout << " waktu, sehingga identik pada setiap mesin dan eksekusi.\n";
return 0;
}Output yang Dihasilkan:
text
Sistem Pencarian dan Pengurutan — dataset mt19937 seed 42
Ringkasan dataset (8 nilai pertama, minimum, maksimum):
n=1000 pertama: 374540 796543 950715 183434 731994 779691 598659 596850 min 520 maks 997741
n=10000 pertama: 374540 796543 950715 183434 731994 779691 598659 596850 min 11 maks 999718
n=100000 pertama: 374540 796543 950715 183434 731994 779691 598659 596850 min 5 maks 999974
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
Kesimpulan:
- cariLinear tumbuh sebanding n; cariBinary hanya ~log2 n
(lihat kolom binary (absen): hanya naik 9 -> 13 -> 16
saat n naik 1000 -> 10000 -> 100000).
- Kedua algoritma pengurutan tumbuh sekitar n log2 n dan
menghasilkan urutan yang sama; quick sort rata-rata lebih
sedikit melakukan perbandingan pada data acak ini.
- Seluruh angka adalah hasil penghitungan, bukan pengukuran
waktu, sehingga identik pada setiap mesin dan eksekusi.Laporan itu padat, jadi mari kita baca seksi demi seksi. Ringkasan dataset memperlihatkan delapan nilai pertama yang identik pada ketiga ukuran — properti potongan aliran dari bagian 1 — sementara minimumnya turun dari 520 ke 11 lalu 5: semakin banyak sampel dari rentang yang sama, semakin besar peluang menangkap nilai ekstrem, dan maksimumnya mendekati batas 1.000.000 dengan pola yang sama. Tabel pencarian mengulang temuan bagian 3 pada target yang ada dan yang absen: linear membayar n perbandingan, binary hanya 9 → 13 → 16. Tabel pengurutan menambahkan kolom pemindahan yang melengkapi analisis bagian 3 — quick sort 4.816 pertukaran lawan 9.976 salinan merge sort pada n=1.000 — dan kolom terurut yang memastikan kedua algoritma menghasilkan urutan yang sama persis. Program lalu mencetak kesimpulannya sendiri; teks itu bukan hiasan, melainkan ringkasan yang wajib mampu kita buktikan dengan tabel di atasnya.
Mengukur Waktu Eksekusi: Chrono, Flag Optimisasi, dan VM 2 Core #
Penghitung menjawab “berapa banyak kerja”, tetapi kadang kita juga ingin tahu “berapa lama dinding jam bergerak”. Standar C++ menyediakan alatnya melalui header <chrono>:
cpp
Mengukur durasi mergeSort dengan std::chrono (ilustrasi)
#include <chrono>
// di dalam main(), setelah data siap:
auto mulai = std::chrono::steady_clock::now();
mergeSort(data);
auto selesai = std::chrono::steady_clock::now();
std::cout << "mergeSort n=100000: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(selesai - mulai)
.count()
<< " ms\n";Saat pola ini kita jalankan pada VM kursus (2 core, RAM 4 GB, kompilasi -O0) untuk merge sort dan quick sort pada n=100.000, dua putaran berturut-turut menghasilkan:
text
Contoh hasil pengukuran pada VM kursus (2 core, RAM 4 GB)
putaran 1: mergeSort 36 ms, quickSort 27 ms
putaran 2: mergeSort 36 ms, quickSort 27 msAngka itu stabil antar putaran pada mesin ini, tetapi jangan tergoda menggeneralisasinya. Flag optimisasi saja sudah mengubah lanskap: kompilasi ulang yang sama dengan -O2 menghasilkan sekitar 8 ms untuk merge sort dan 6 ms untuk quick sort — lebih dari empat kali lipat lebih cepat tanpa mengubah satu baris algoritma.
Harness Uji: 42 Pemeriksaan, Satu Exit Code #
Langkah penutup proyek: harness uji yang menyalin seluruh inti algoritma dan menguncinya dengan 42 pemeriksaan. File harness tersedia sebagai tests/uji-cari-urut.cpp — salinan yang identik disertakan di bawah agar bisa dibaca utuh:
cpp
// uji-cari-urut.cpp — harness uji untuk proyek Sistem Pencarian dan
// Pengurutan. Memeriksa kebenaran pencarian dan pengurutan pada data kecil
// yang bisa ditelusuri manual, kasus tepi, nilai emas penghitung
// (deterministik), dan stabilitas merge sort. Exit code 0 = semua lulus.
#include <algorithm>
#include <iostream>
#include <random>
#include <string>
#include <utility>
#include <vector>
// ---------- Kode yang diuji (salinan inti cari-urut.cpp) ----------
struct StatistikAlgo {
long long perbandingan = 0;
long long pemindahan = 0;
};
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;
}
template <typename T>
int cariLinear(const std::vector<T>& data, const T& target,
StatistikAlgo* stat = nullptr) {
for (std::size_t i = 0; i < data.size(); ++i) {
if (stat) {
++stat->perbandingan;
}
if (data[i] == target) {
return static_cast<int>(i);
}
}
return -1;
}
template <typename T>
int cariBinary(const std::vector<T>& data, const T& target,
StatistikAlgo* stat = nullptr) {
int kiri = 0;
int kanan = static_cast<int>(data.size()) - 1;
while (kiri <= kanan) {
int tengah = kiri + (kanan - kiri) / 2;
if (stat) {
++stat->perbandingan;
}
if (data[tengah] == target) {
return tengah;
}
if (data[tengah] < target) {
kiri = tengah + 1;
} else {
kanan = tengah - 1;
}
}
return -1;
}
template <typename T>
void mergeSortRekursif(std::vector<T>& data, std::vector<T>& bantu,
std::size_t kiri, std::size_t kanan,
StatistikAlgo* stat) {
if (kanan - kiri < 2) {
return;
}
std::size_t tengah = kiri + (kanan - kiri) / 2;
mergeSortRekursif(data, bantu, kiri, tengah, stat);
mergeSortRekursif(data, bantu, tengah, kanan, stat);
std::size_t i = kiri;
std::size_t j = tengah;
std::size_t k = kiri;
while (i < tengah && j < kanan) {
if (stat) {
++stat->perbandingan;
}
if (data[j] < data[i]) {
bantu[k++] = data[j++];
if (stat) ++stat->pemindahan;
} else {
bantu[k++] = data[i++];
if (stat) ++stat->pemindahan;
}
}
while (i < tengah) {
bantu[k++] = data[i++];
if (stat) ++stat->pemindahan;
}
while (j < kanan) {
bantu[k++] = data[j++];
if (stat) ++stat->pemindahan;
}
for (std::size_t x = kiri; x < kanan; ++x) {
data[x] = bantu[x];
}
}
template <typename T>
void mergeSort(std::vector<T>& data, StatistikAlgo* stat = nullptr) {
std::vector<T> bantu(data.size());
mergeSortRekursif(data, bantu, 0, data.size(), stat);
}
template <typename T>
int partisi(std::vector<T>& data, int kiri, int kanan, StatistikAlgo* stat) {
int tengah = kiri + (kanan - kiri) / 2;
std::swap(data[tengah], data[kanan]);
T pivot = data[kanan];
int batas = kiri;
for (int j = kiri; j < kanan; ++j) {
if (stat) {
++stat->perbandingan;
}
if (data[j] < pivot) {
std::swap(data[j], data[batas]);
++batas;
if (stat) ++stat->pemindahan;
}
}
std::swap(data[batas], data[kanan]);
return batas;
}
template <typename T>
void quickSortRekursif(std::vector<T>& data, int kiri, int kanan,
StatistikAlgo* stat) {
if (kiri >= kanan) {
return;
}
int posisiPivot = partisi(data, kiri, kanan, stat);
quickSortRekursif(data, kiri, posisiPivot - 1, stat);
quickSortRekursif(data, posisiPivot + 1, kanan, stat);
}
template <typename T>
void quickSort(std::vector<T>& data, StatistikAlgo* stat = nullptr) {
if (data.empty()) {
return;
}
quickSortRekursif(data, 0, static_cast<int>(data.size()) - 1, stat);
}
// ---------- Mini harness ----------
static int jumlahLulus = 0;
static int jumlahGagal = 0;
static std::string namaUjiAktif;
#define MULAI_UJI(nama) namaUjiAktif = (nama)
#define CHECK_TRUE(kondisi, deskripsi) cekBoolean((kondisi), (deskripsi))
#define CHECK_EQ(aktual, diharapkan) cekSama((aktual), (diharapkan), #aktual)
void cekBoolean(bool kondisi, const std::string& deskripsi) {
if (kondisi) {
++jumlahLulus;
std::cout << "[ LULUS ] " << namaUjiAktif << " - " << deskripsi << "\n";
} else {
++jumlahGagal;
std::cout << "[ GAGAL ] " << namaUjiAktif << " - " << deskripsi << "\n";
}
}
template <typename T, typename U>
void cekSama(const T& aktual, const U& diharapkan, const char* ekspresi) {
if (aktual == diharapkan) {
++jumlahLulus;
std::cout << "[ LULUS ] " << namaUjiAktif << " - " << ekspresi << "\n";
} else {
++jumlahGagal;
std::cout << "[ GAGAL ] " << namaUjiAktif << " - " << ekspresi
<< " (aktual " << aktual << ", diharapkan " << diharapkan
<< ")\n";
}
}
// ---------- Test case ----------
const std::vector<int> DATA_KECIL = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
void ujiCariLinear() {
MULAI_UJI("cariLinear");
for (std::size_t i = 0; i < DATA_KECIL.size(); ++i) {
CHECK_EQ(cariLinear(DATA_KECIL, DATA_KECIL[i]),
static_cast<int>(i));
}
CHECK_EQ(cariLinear(DATA_KECIL, -1), -1); // absen di bawah rentang
CHECK_EQ(cariLinear(DATA_KECIL, 24), -1); // absen di tengah rentang
CHECK_EQ(cariLinear(DATA_KECIL, 100), -1); // absen di atas rentang
}
void ujiCariBinary() {
MULAI_UJI("cariBinary");
for (std::size_t i = 0; i < DATA_KECIL.size(); ++i) {
CHECK_EQ(cariBinary(DATA_KECIL, DATA_KECIL[i]),
static_cast<int>(i));
}
CHECK_EQ(cariBinary(DATA_KECIL, 2), 0); // elemen pertama
CHECK_EQ(cariBinary(DATA_KECIL, 91), 9); // elemen terakhir
CHECK_EQ(cariBinary(DATA_KECIL, 24), -1);
}
void ujiPengurutanDataAcak() {
MULAI_UJI("pengurutan data acak");
std::vector<int> asli = buatDataset(1000, 7);
std::vector<int> salinanMerge = asli;
std::vector<int> salinanQuick = asli;
std::vector<int> oracle = asli;
std::sort(oracle.begin(), oracle.end());
mergeSort(salinanMerge);
quickSort(salinanQuick);
CHECK_TRUE(salinanMerge == oracle, "mergeSort sama dengan std::sort");
CHECK_TRUE(salinanQuick == oracle, "quickSort sama dengan std::sort");
}
void ujiKasusTepi() {
MULAI_UJI("kasus tepi");
std::vector<int> kosong;
mergeSort(kosong);
quickSort(kosong);
CHECK_TRUE(kosong.empty(), "vector kosong tetap kosong setelah diurutkan");
CHECK_EQ(cariLinear(kosong, 1), -1);
CHECK_EQ(cariBinary(kosong, 1), -1);
std::vector<int> satu = {42};
mergeSort(satu);
CHECK_EQ(satu[0], 42);
std::vector<int> ganda = {7, 7, 7, 7};
std::vector<int> pembanding = {7, 7, 7, 7};
quickSort(ganda);
CHECK_TRUE(ganda == pembanding, "semua elemen sama tetap terurut");
}
void ujiNilaiEmasPenghitung() {
MULAI_UJI("nilai emas penghitung");
std::vector<int> asli = buatDataset(1000, 42);
std::vector<int> terurut = asli;
mergeSort(terurut);
StatistikAlgo linAbsen;
cariLinear(asli, -1, &linAbsen);
CHECK_EQ(linAbsen.perbandingan, 1000); // satu per elemen
StatistikAlgo binAbsen;
cariBinary(terurut, -1, &binAbsen);
CHECK_EQ(binAbsen.perbandingan, 9); // ~log2 1000
StatistikAlgo statMerge;
std::vector<int> salinanMerge = asli;
mergeSort(salinanMerge, &statMerge);
CHECK_EQ(statMerge.perbandingan, 8703);
CHECK_EQ(statMerge.pemindahan, 9976);
StatistikAlgo statQuick;
std::vector<int> salinanQuick = asli;
quickSort(salinanQuick, &statQuick);
CHECK_EQ(statQuick.perbandingan, 11031);
CHECK_EQ(statQuick.pemindahan, 4816);
}
void ujiStabilitasMergeSort() {
MULAI_UJI("stabilitas mergeSort");
struct Rekaman {
int kunci;
int urutanDatang;
bool operator<(const Rekaman& lainnya) const {
return kunci < lainnya.kunci; // kunci sama dianggap setara
}
};
std::vector<Rekaman> data = {
{5, 0}, {3, 1}, {5, 2}, {1, 3}, {3, 4}, {5, 5},
};
mergeSort(data);
bool stabil = true;
for (std::size_t i = 1; i < data.size(); ++i) {
if (data[i - 1].kunci == data[i].kunci &&
data[i - 1].urutanDatang > data[i].urutanDatang) {
stabil = false;
}
}
CHECK_TRUE(stabil, "urutan asli kunci sama tetap terjaga");
}
void ujiDeterminismeDataset() {
MULAI_UJI("determinisme dataset");
CHECK_TRUE(buatDataset(100, 42) == buatDataset(100, 42),
"seed sama menghasilkan dataset identik");
CHECK_TRUE(buatDataset(100, 42) != buatDataset(100, 43),
"seed berbeda menghasilkan dataset berbeda");
}
int main() {
ujiCariLinear();
ujiCariBinary();
ujiPengurutanDataAcak();
ujiKasusTepi();
ujiNilaiEmasPenghitung();
ujiStabilitasMergeSort();
ujiDeterminismeDataset();
std::cout << "\nringkasan: " << jumlahLulus << " lulus, " << jumlahGagal
<< " gagal\n";
return jumlahGagal == 0 ? 0 : 1;
}Output yang Dihasilkan:
text
[ LULUS ] cariLinear - cariLinear(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariLinear - cariLinear(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariLinear - cariLinear(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariLinear - cariLinear(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariLinear - cariLinear(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariLinear - cariLinear(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariLinear - cariLinear(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariLinear - cariLinear(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariLinear - cariLinear(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariLinear - cariLinear(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariLinear - cariLinear(DATA_KECIL, -1)
[ LULUS ] cariLinear - cariLinear(DATA_KECIL, 24)
[ LULUS ] cariLinear - cariLinear(DATA_KECIL, 100)
[ LULUS ] cariBinary - cariBinary(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariBinary - cariBinary(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariBinary - cariBinary(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariBinary - cariBinary(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariBinary - cariBinary(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariBinary - cariBinary(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariBinary - cariBinary(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariBinary - cariBinary(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariBinary - cariBinary(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariBinary - cariBinary(DATA_KECIL, DATA_KECIL[i])
[ LULUS ] cariBinary - cariBinary(DATA_KECIL, 2)
[ LULUS ] cariBinary - cariBinary(DATA_KECIL, 91)
[ LULUS ] cariBinary - cariBinary(DATA_KECIL, 24)
[ LULUS ] pengurutan data acak - mergeSort sama dengan std::sort
[ LULUS ] pengurutan data acak - quickSort sama dengan std::sort
[ LULUS ] kasus tepi - vector kosong tetap kosong setelah diurutkan
[ LULUS ] kasus tepi - cariLinear(kosong, 1)
[ LULUS ] kasus tepi - cariBinary(kosong, 1)
[ LULUS ] kasus tepi - satu[0]
[ LULUS ] kasus tepi - semua elemen sama tetap terurut
[ LULUS ] nilai emas penghitung - linAbsen.perbandingan
[ LULUS ] nilai emas penghitung - binAbsen.perbandingan
[ LULUS ] nilai emas penghitung - statMerge.perbandingan
[ LULUS ] nilai emas penghitung - statMerge.pemindahan
[ LULUS ] nilai emas penghitung - statQuick.perbandingan
[ LULUS ] nilai emas penghitung - statQuick.pemindahan
[ LULUS ] stabilitas mergeSort - urutan asli kunci sama tetap terjaga
[ LULUS ] determinisme dataset - seed sama menghasilkan dataset identik
[ LULUS ] determinisme dataset - seed berbeda menghasilkan dataset berbeda
ringkasan: 42 lulus, 0 gagalTujuh kelompok uji membagi tugas menjaga kebenaran:
- cariLinear: setiap elemen
DATA_KECILditemukan pada indeksnya sendiri, dan tiga bentuk ketiadaan (di bawah rentang, di tengah rentang, di atas rentang) semua mengembalikan-1. - cariBinary: sepuluh target yang ada ditemukan, termasuk kedua ujung rentang — lokasi klasik bug off-by-one — dan target absen dikembalikan dengan benar.
- Pengurutan data acak: 1.000 elemen dari seed 7 diurutkan oleh kedua algoritma, lalu dibandingkan dengan
std::sortsebagai oracle — dua implementasi manual harus menghasilkan urutan yang identik dengan versi standard library. - Kasus tepi: vector kosong tetap kosong, vector satu elemen tetap benar, dan vector berisi empat nilai sama tidak merusak partisi quick sort.
- Nilai emas penghitung: 1.000 perbandingan linear untuk target absen, 9 untuk binary, serta 8.703/9.976 untuk merge sort dan 11.031/4.816 untuk quick sort pada seed 42 — angka yang sama dengan tabel program final.
- Stabilitas merge sort: rekaman berkunci ganda (5, 3, 5, 1, 3, 5) diurutkan dan urutan kedatangan elemen sekunci tetap terjaga — bukti langsung atas keputusan
<ketat di bagian 2. - Determinisme dataset: seed sama menghasilkan dataset identik, seed berbeda menghasilkan dataset berbeda.
Program keluar dengan exit code 0 — ringkasan: 42 lulus, 0 gagal — dan kelompok kelima adalah yang paling khas dari proyek ini: nilai emasnya adalah angka kerja algoritma, sesuatu yang hanya bisa diuji bila implementasi dan dataset sama-sama deterministik.
Dengan itu proyek Sistem Pencarian dan Pengurutan tuntas: data yang adil, algoritma yang dipahami, harga yang dihitung, dan perilaku yang terkunci oleh pengujian. Proyek berikutnya membawa kita keluar dari memori dan angka menuju dunia berkas — Aplikasi Pengelola File dengan std::filesystem untuk menjelajahi direktori, mencari dan menyaring berkas, serta membaca metadata — dan pola disiplin yang kita bangun di sini akan terus terpakai.
Rujukan resmi: std::chrono::steady_clock (cppreference) , std::sort (cppreference) .