Strategi Pengujian

Algoritma yang rumit jarang benar pada percobaan pertama. Tanpa strategi pengujian yang jelas, kita akan terjebak debugging symptom, bukan akar masalah. Pada Chapter ini kita akan membangun kerangka berpikir sistematis: mulai dari test pyramid (unit, integration, edge), perbedaan black box vs white box, hingga struktur test case sederhana yang dapat dijalankan tanpa framework tambahan. Tujuan akhirnya: ketika menulis algoritma baru, kita tahu persis jenis test apa yang harus disiapkan sebelum kode dianggap benar.

Test Pyramid: Unit, Integration, Edge #

Test pyramid adalah metafora distribusi test. Banyak test kecil dan cepat di bagian bawah, sedikit test lambat dan luas di bagian atas.

Black Box vs White Box #

Pendekatan pengujian dapat dilihat dari dua sisi:

• Black box: kita hanya tahu input dan output yang diharapkan, tanpa peduli implementasi internal. Cocok untuk verifikasi publik API. Contoh: “fungsi sort harus mengembalikan array terurut menaik”.
• White box: kita memanfaatkan pengetahuan struktur internal untuk merancang test yang menempuh cabang-cabang tertentu (branch coverage, path coverage). Contoh: “saat pivot adalah elemen minimum, partition harus tetap O(n)”.

Untuk DSA, kombinasi keduanya ideal: black box untuk validasi semantik, white box untuk menutup cabang yang jarang dieksekusi (rekursi pangkal, kasus rotasi pohon, dll.).

Mekanisme: Apa yang Diuji di Setiap Lapisan #

1. Unit test menguji satu fungsi murni — input tertentu menghasilkan output tertentu. Bila fungsi punya efek samping (mutasi state), test harus mengamati state sebelum dan sesudah.
2. Integration test menggabungkan dua fungsi atau lebih, lalu mengamati apakah komposisi tetap benar (misalnya reverse(sort(a)) menghasilkan array terurut menurun).
3. Edge case memilih input batas yang paling sering memunculkan bug: koleksi kosong, satu elemen, elemen maksimum/minimum, input yang sudah terurut, input dengan duplikat.
4. Property-based menguji sifat yang selalu benar (invariant) pada ribuan input acak — misalnya “panjang output sort(a) sama dengan panjang input”.

Kode: Harness Pengujian Sederhana Tanpa Framework #

Kita tidak selalu butuh GoogleTest untuk memulai. Harness sederhana berikut cukup untuk mayoritas algoritma DSA — sebuah struct TestCase dengan nama, callable, dan expected value.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>

struct TestCase {
    std::string name;
    std::function<int()> run;
    int expected;
};

// Versi bug: best dimulai dari 0 — salah untuk semua elemen negatif.
int max_subarray_bug(const std::vector<int>& a) {
    int best = 0;
    int cur = 0;
    for (int x : a) {
        cur += x;
        if (cur < 0) cur = 0;
        best = std::max(best, cur);
    }
    return best;
}

// Versi benar: best dimulai dari elemen pertama.
int max_subarray_ok(const std::vector<int>& a) {
    if (a.empty()) return 0;
    int best = a[0];
    int cur = a[0];
    for (size_t i = 1; i < a.size(); ++i) {
        cur = std::max(a[i], cur + a[i]);
        best = std::max(best, cur);
    }
    return best;
}

int main() {
    std::vector<TestCase> tests = {
        {"empty",      [&] { return max_subarray_ok({}); },                          0},
        {"single_pos", [&] { return max_subarray_ok({7}); },                         7},
        {"single_neg", [&] { return max_subarray_ok({-3}); },                        -3},
        {"mixed",      [&] { return max_subarray_ok({-2,1,-3,4,-1,2,1,-5,4}); },     6},
        {"all_neg",    [&] { return max_subarray_ok({-5,-2,-8,-1}); },              -1},
        {"all_pos",    [&] { return max_subarray_ok({1,2,3,4}); },                   10},
    };

    int pass = 0, fail = 0;
    for (const auto& t : tests) {
        int got = t.run();
        bool ok = (got == t.expected);
        std::cout << (ok ? "[OK]   " : "[FAIL] ") << t.name
                  << " got=" << got << " expected=" << t.expected << '\n';
        ok ? pass++ : fail++;
    }
    std::cout << "\nHasil: " << pass << " pass, " << fail << " fail dari "
              << tests.size() << " test case.\n";

    std::cout << "\n--- Versi bug pada input all-neg ---\n";
    std::vector<int> neg = {-5,-2,-8,-1};
    std::cout << "max_subarray_bug({-5,-2,-8,-1}) = " << max_subarray_bug(neg) << '\n';
    std::cout << "max_subarray_ok({-5,-2,-8,-1})  = " << max_subarray_ok(neg) << '\n';
    return 0;
}

Output yang Dihasilkan:

[OK]   empty got=0 expected=0
[OK]   single_pos got=7 expected=7
[OK]   single_neg got=-3 expected=-3
[OK]   mixed got=6 expected=6
[OK]   all_neg got=-1 expected=-1
[OK]   all_pos got=10 expected=10

Hasil: 6 pass, 0 fail dari 6 test case.

--- Versi bug pada input all-neg ---
max_subarray_bug({-5,-2,-8,-1}) = 0
max_subarray_ok({-5,-2,-8,-1})  = -1

Bedah Kode Baris-per-Baris #

1. struct TestCase { std::string name; std::function<int()> run; int expected; };: membungkus tiga komponen test — nama (untuk laporan), callable (fungsi yang diuji berserta argumennya), dan expected value. Memakai std::function memungkinkan lambda capture-by-reference sehingga kita bisa menyusun inline.
2. max_subarray_bug: algoritma Kadane versi naif dengan best = 0. Untuk array semua-negatif, jawaban yang benar adalah elemen terbesar (misalnya -1 pada {-5,-2,-8,-1}), tetapi fungsi ini mengembalikan 0 karena best tidak pernah di-reset ke nilai negatif.
3. max_subarray_ok: inisialisasi best = a[0] dan cur = a[0], kemudian iterasi dari indeks 1. Formula cur = max(a[i], cur + a[i]) memilih antara memulai subarray baru atau melanjutkan subarray berjalan.
4. std::vector<TestCase> tests = {...}: daftar test case sebagai initializer list. Tiap entri adalah lambda yang langsung memanggil max_subarray_ok dengan input konkret.
5. bool ok = (got == t.expected);: perbandingan sederhana. Hasil dihitung sebagai pass atau fail, dicetak dengan label [OK] atau [FAIL].
6. max_subarray_bug(neg): demonstrasi terakhir menunjukkan bagaimana versi bug mengembalikan 0 sedangkan versi benar mengembalikan -1. Inilah mengapa test “all_neg” adalah edge case wajib untuk algoritma subarray.

Strategi Pemilihan Test Case #

Tabel berikut adalah checklist kategori input yang harus dipertimbangkan untuk setiap algoritma DSA:

Kapan Berpindah ke Framework #

Harness sederhana di atas cukup untuk 20–30 test case. Begitu jumlah test tumbuh atau kita membutuhkan fixtures, parameterized tests, atau setup/teardown, beralih ke GoogleTest atau Catch2 adalah pilihan tepat. Bab unit-testing akan membahasnya lebih dalam.

Ringkasan #

• Test pyramid membagi pengujian menjadi lapisan unit, integration, edge, dan property-based.
• Black box menguji dari sudut API publik; white box memanfaatkan struktur internal untuk menutup cabang yang jarang dieksekusi.
• Harness sederhana berbasis struct TestCase + std::function cukup untuk mayoritas DSA tanpa dependensi eksternal.
• Checklist kategori input (kosong, satu elemen, semua sama, sorted, reverse sorted, semua negatif) memandu pemilihan edge case.
• Versi bug max_subarray dengan best = 0 menggambarkan bagaimana test “all_neg” menemukan bug yang tidak terlihat pada uji acak.