Bagian 2: Mengimplementasikan Algoritma

Standard library sudah menyediakan std::find, std::binary_search, dan std::sort — lalu mengapa kita menulisnya sendiri? Karena tujuan proyek ini bukan sekadar mengurutkan data, melainkan mengukur harga kerja setiap algoritma, dan penghitung hanya bisa dipasang di kode milik sendiri. Ada nilai belajarnya juga: empat algoritma ini adalah latihan yang memaksa kita berhadapan dengan batas indeks, syarat prasyarat, dan pertukaran memori-lawan-kecepatan. Pada bagian ini kita membaca implementasi manual di src/cari-urut.cpp algoritma demi algoritma, lalu membuktikan kebenarannya dengan program uji kecil.

Satu catatan sebelum mulai: semua fungsi di program final menerima parameter StatistikAlgo* stat = nullptr di akhir daftar argumennya. Jalur penghitungnya (if (stat)) sengaja dibawa sejak sekarang agar kita tidak menyentuh algoritma lagi di bagian 3 — untuk pembahasan bagian ini, cukup anggap parameter itu tempat penampung angka yang nanti kita isi.

Linear Search: Menyisir dari Depan #

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

Implementasinya sederhana dan jujur: kunjungi elemen satu per satu dari indeks 0, kembalikan indeks pertama yang cocok. Bila seluruh data tersisir tanpa menemukan target, -1 dikembalikan sebagai tanda absen — nilai yang mustahil menjadi indeks yang sah, sehingga pemanggil tidak bisa salah menafsirkannya. Karena tidak mensyaratkan apa pun tentang urutan data, linear search adalah satu-satunya pilihan pada data acak. Fungsi ini template <typename T> sehingga bekerja untuk tipe apa pun yang punya operator== — pada harness nanti ia tetap dipakai apa adanya untuk std::vector<int>.

Binary Search: Membagi Dua Setiap Langkah #

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

Bedah baris demi baris:

kiri = 0; kanan = size - 1;: ruang pencarian ditutup sebagai rentang [kiri, kanan] — kedua ujung inklusif.
tengah = kiri + (kanan - kiri) / 2;: rumus tengah yang aman. Menulis (kiri + kanan) / 2 juga benar untuk ukuran data kecil, tetapi bisa meluap pada ukuran ekstrem; bentuk selisih ini kebal masalah itu.
data[tengah] == target: keberhasilan — kembalikan indeksnya seketika.
data[tengah] < target: target pasti berada di setengah kanan, jadi kiri = tengah + 1; selain itu target pasti di setengah kiri, jadi kanan = tengah - 1. Setiap putaran memangkas ruang pencarian menjadi separuhnya.
while (kiri <= kanan): loop berhenti saat ruang pencarian habis; yang berhenti tanpa menemukan apa pun mengembalikan -1.

Merge Sort: Bagi, Urutkan, Gabungkan #

cpp
src/cari-urut.cpp — mergeSortRekursif dan mergeSort
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);
}

Strateginya divide and conquer: pecah rentang menjadi dua setengah, urutkan masing-masing secara rekursif, lalu gabungkan dua rentang yang sudah terurut menjadi satu. Pemecahannya dijaga dalam satu baris penting: if (kanan - kiri < 2) return; — rentang berisi 0 atau 1 elemen dianggap sudah terurut, dan itulah dasar rekurasi yang mencegahnya berputar selamanya. Penggabungannya memakai tiga penunjuk: i menyisir setengah kiri, j setengah kanan, dan k menulis ke buffer bantu. Perbandingan data[j] < data[i] sengaja memakai < ketat, bukan <=, sehingga saat dua elemen setara, yang dari kiri diambil lebih dulu — keputusan kecil inilah yang menjadikan merge sort stabil, dan harness di bagian 4 mengujinya secara eksplisit dengan rekaman berkunci ganda. Setelah salah satu setengah habis, sisa setengah lainnya disalin utuh, lalu isi buffer ditulis kembali ke data.

Harga keanggunan itu adalah memori: mergeSort mengalokasikan satu buffer seukuran data di awal dan memakainya berulang — itulah O(n) memori tambahan yang selalu disebut sebagai kelemahan merge sort.

Quick Sort: Partisi di Sekitar Pivot #

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

partisi adalah jantung quick sort, dan ia bekerja di tempat (in-place) tanpa buffer tambahan:

Pivot dipilih dari tengah lalu std::swap ke ujung kanan supaya mudah dijaga — pivot elemen tengah membuat data yang sudah terurut tidak jatuh ke kasus terburuk yang terjadi bila pivot selalu diambil dari ujung.
batas menandai tepi zona “lebih kecil dari pivot”; semua elemen di kiri batas sudah dipastikan kecil.
data[j] < pivot: elemen yang lebih kecil ditukar ke posisi batas, lalu zona memanjang satu langkah. Elemen yang setara atau lebih besar dibiarkan di kanan.
std::swap(data[batas], data[kanan]) menempatkan pivot di posisi akhirnya — indeks batas dikembalikan, dan dua sisi pivot diurutkan rekursif oleh quickSortRekursif sampai rentangnya menyusut ke nol atau satu elemen.

Quick sort menukar jaminan dengan kecepatan: rata-ratanya cepat dan hemat memori, tetapi kasus terburuknya O(n²) — terjadi bila pivot selalu jatuh di ujung — sementara merge sort dijamin O(n log n) pada masukan apa pun. Penghitung di bagian 3 memperlihatkan pertukaran ini dalam angka nyata.

Menguji Empat Algoritma pada Data Kecil #

Sebelum data 100.000 elemen, kebenaran lebih dulu diuji pada data kecil yang bisa diperiksa mata:

cpp
algoritma-dasar.cpp — program lengkap untuk bagian ini
// algoritma-dasar.cpp — Bagian 2: implementasi manual pencarian dan pengurutan.
// Empat algoritma inti proyek diuji pada data kecil yang bisa diperiksa
// dengan mata: cariLinear, cariBinary, mergeSort, dan quickSort.
#include <iostream>
#include <vector>

// ---------- Pencarian ----------
template <typename T>
int cariLinear(const std::vector<T>& data, const T& target) {
    for (std::size_t i = 0; i < data.size(); ++i) {
        if (data[i] == target) {
            return static_cast<int>(i);
        }
    }
    return -1;
}

template <typename T>
int cariBinary(const std::vector<T>& data, const T& target) {
    int kiri = 0;
    int kanan = static_cast<int>(data.size()) - 1;
    while (kiri <= kanan) {
        int tengah = kiri + (kanan - kiri) / 2;
        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 gabungkan(std::vector<T>& data, std::vector<T>& bantu, std::size_t kiri,
               std::size_t tengah, std::size_t kanan) {
    std::size_t i = kiri;
    std::size_t j = tengah;
    std::size_t k = kiri;
    while (i < tengah && j < kanan) {
        if (data[j] < data[i]) {
            bantu[k++] = data[j++];
        } else {
            bantu[k++] = data[i++]; // ambil kiri dulu agar stabil
        }
    }
    while (i < tengah) bantu[k++] = data[i++];
    while (j < kanan) bantu[k++] = data[j++];
    for (std::size_t x = kiri; x < kanan; ++x) data[x] = bantu[x];
}

template <typename T>
void mergeSortRekursif(std::vector<T>& data, std::vector<T>& bantu,
                       std::size_t kiri, std::size_t kanan) {
    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);
    mergeSortRekursif(data, bantu, tengah, kanan);
    gabungkan(data, bantu, kiri, tengah, kanan);
}

template <typename T>
void mergeSort(std::vector<T>& data) {
    std::vector<T> bantu(data.size());
    mergeSortRekursif(data, bantu, 0, data.size());
}

// ---------- Pengurutan: quick sort ----------
template <typename T>
int partisi(std::vector<T>& data, int kiri, int kanan) {
    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 (data[j] < pivot) {
            std::swap(data[j], data[batas]);
            ++batas;
        }
    }
    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) {
    if (kiri >= kanan) {
        return;
    }
    int posisiPivot = partisi(data, kiri, kanan);
    quickSortRekursif(data, kiri, posisiPivot - 1);
    quickSortRekursif(data, posisiPivot + 1, kanan);
}

template <typename T>
void quickSort(std::vector<T>& data) {
    if (!data.empty()) {
        quickSortRekursif(data, 0, static_cast<int>(data.size()) - 1);
    }
}

// ---------- Uji pada data kecil ----------
void cetak(const std::string& label, const std::vector<int>& data) {
    std::cout << label;
    for (int nilai : data) {
        std::cout << ' ' << nilai;
    }
    std::cout << '\n';
}

int main() {
    const std::vector<int> terurut = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

    std::cout << "Pencarian pada data terurut:\n";
    std::cout << "cariLinear(23)  -> indeks " << cariLinear(terurut, 23) << '\n';
    std::cout << "cariBinary(23)  -> indeks " << cariBinary(terurut, 23) << '\n';
    std::cout << "cariBinary(91)  -> indeks " << cariBinary(terurut, 91) << '\n';
    std::cout << "cariBinary(2)   -> indeks " << cariBinary(terurut, 2) << '\n';
    std::cout << "cariLinear(24)  -> indeks " << cariLinear(terurut, 24)
              << " (tidak ada)\n";
    std::cout << "cariBinary(24)  -> indeks " << cariBinary(terurut, 24)
              << " (tidak ada)\n";

    std::vector<int> dataMerge = {38, 2, 91, 16, 72, 5, 23, 8};
    std::cout << "\nmergeSort:\n";
    cetak("  sebelum:", dataMerge);
    mergeSort(dataMerge);
    cetak("  sesudah:", dataMerge);

    std::vector<int> dataQuick = {23, 8, 56, 2, 91, 16};
    std::cout << "\nquickSort:\n";
    cetak("  sebelum:", dataQuick);
    quickSort(dataQuick);
    cetak("  sesudah:", dataQuick);
    return 0;
}

bash
g++ -std=c++23 -Wall -Wextra algoritma-dasar.cpp -o algoritma-dasar
./algoritma-dasar

Output yang Dihasilkan:

text
Pencarian pada data terurut:
cariLinear(23)  -> indeks 5
cariBinary(23)  -> indeks 5
cariBinary(91)  -> indeks 9
cariBinary(2)   -> indeks 0
cariLinear(24)  -> indeks -1 (tidak ada)
cariBinary(24)  -> indeks -1 (tidak ada)

mergeSort:
  sebelum: 38 2 91 16 72 5 23 8
  sesudah: 2 5 8 16 23 38 72 91

quickSort:
  sebelum: 23 8 56 2 91 16
  sesudah: 2 8 16 23 56 91

Dari output itu: cariLinear dan cariBinary sepakat pada indeks 5 untuk target 23, dan sama-sama melapor -1 untuk 24 yang memang absen — dua pendekatan berbeda, jawaban yang sama. cariBinary menemukan elemen pertama (indeks 0) dan terakhir (indeks 9) tanpa keluhan, ujung rentang yang paling sering jadi sumber bug off-by-one. Kedua sort menghasilkan urutan naik yang benar dari data awal yang berantakan, dan program keluar dengan exit code 0. Keempat algoritma kini terbukti benar pada skala kecil; bagian 3 menghitung berapa yang mereka bayar saat data membesar.

Rujukan resmi: function template (cppreference) , std::swap (cppreference) .