Bagian 2: Implementasi Algoritma

Pada bagian ini kita mengimplementasikan enam fungsi sorting dengan tanda tangan void sort(std::vector<int>&) yang telah ditetapkan pada Bagian 1. Setiap algoritma ditulis ulang dari nol (kecuali stdSort yang membungkus std::sort) agar benchmark jujur — tidak ada trik implementasi yang tidak adil. Untuk quicksort, kita pakai pivot terakhir yang sengaja rawan worst-case agar benchmark menyingkap kelemahannya pada data sorted.

Bubble Sort #

Bubble sort adalah algoritma paling sederhana: bandingkan pasangan elemen berdekatan, tukar bila tidak urut, ulangi hingga tidak ada pertukaran.

cpp
void bubbleSort(std::vector<int>& v) {
    int n = (int)v.size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (v[j] > v[j + 1]) {
                std::swap(v[j], v[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;   // early exit bila sudah terurut
    }
}

Insertion Sort #

Insertion sort menyisipkan setiap elemen ke posisi yang tepat di bagian kiri yang sudah terurut. Efisien untuk data hampir terurut.

cpp
void insertionSort(std::vector<int>& v) {
    for (size_t i = 1; i < v.size(); ++i) {
        int key = v[i];
        int j = (int)i - 1;
        while (j >= 0 && v[j] > key) {
            v[j + 1] = v[j];
            --j;
        }
        v[j + 1] = key;
    }
}

Merge Sort #

Merge sort membagi array menjadi dua, mengurutkan rekursif, lalu menggabungkan. Stabil dan selalu O(n log n), tetapi membutuhkan memori tambahan O(n) untuk buffer merge.

cpp
static void mergeRec(std::vector<int>& v, std::vector<int>& buf,
        size_t lo, size_t hi) {
    if (hi - lo <= 1) return;
    size_t mid = lo + (hi - lo) / 2;
    mergeRec(v, buf, lo, mid);
    mergeRec(v, buf, mid, hi);
    size_t i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (v[i] <= v[j]) buf[k++] = v[i++];
        else              buf[k++] = v[j++];
    }
    while (i < mid) buf[k++] = v[i++];
    while (j < hi)  buf[k++] = v[j++];
    for (size_t p = lo; p < hi; ++p) v[p] = buf[p];
}

void mergeSort(std::vector<int>& v) {
    if (v.size() < 2) return;
    std::vector<int> buf(v.size());
    mergeRec(v, buf, 0, v.size());
}

Quick Sort (Pivot Terakhir) #

Quick sort memilih pivot (di sini elemen terakhir), partisi array menjadi dua (lebih kecil dan lebih besar dari pivot), lalu mengurutkan rekursif. Pemilihan pivot terakhir membuat algoritma rentan worst-case pada data sorted/reversed — sesuatu yang akan benchmark konfirmasi.

cpp
static int partition(std::vector<int>& v, int lo, int hi) {
    int pivot = v[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; ++j) {
        if (v[j] <= pivot) {
            ++i;
            std::swap(v[i], v[j]);
        }
    }
    std::swap(v[i + 1], v[hi]);
    return i + 1;
}

static void quickRec(std::vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(v, lo, hi);
    quickRec(v, lo, p - 1);
    quickRec(v, p + 1, hi);
}

void quickSort(std::vector<int>& v) {
    if (v.size() < 2) return;
    quickRec(v, 0, (int)v.size() - 1);
}

Heap Sort #

Heap sort membangun max-heap in-place, lalu menukar root dengan elemen terakhir dan memperbaiki heap. Tidak stabil tetapi selalu O(n log n).

cpp
static void heapify(std::vector<int>& v, int n, int i) {
    int largest = i;
    int l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && v[l] > v[largest]) largest = l;
    if (r < n && v[r] > v[largest]) largest = r;
    if (largest != i) {
        std::swap(v[i], v[largest]);
        heapify(v, n, largest);
    }
}

void heapSort(std::vector<int>& v) {
    int n = (int)v.size();
    for (int i = n / 2 - 1; i >= 0; --i) heapify(v, n, i);
    for (int i = n - 1; i > 0; --i) {
        std::swap(v[0], v[i]);
        heapify(v, i, 0);
    }
}

Wrapper std::sort #

Wrapper memungkinkan std::sort dipanggil dengan tanda tangan yang sama. Tidak ada optimasi tambahan — kita percaya implementasi STL.

cpp
void stdSort(std::vector<int>& v) {
    std::sort(v.begin(), v.end());
}

Program Verifikasi #

Sebelum benchmark, kita verifikasi bahwa keenam fungsi benar-benar mengurutkan dengan benar. Program berikut menguji setiap algoritma pada array acak dan memeriksa hasilnya dengan std::is_sorted.

cpp
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

// (definisi keenam fungsi sort di atas diletakkan di sini)

int main() {
    std::vector<int> original = {5, 2, 8, 1, 9, 3, 7, 4, 6, 0};

    std::vector<void(*)(std::vector<int>&)> fns = {
        bubbleSort, insertionSort, mergeSort, quickSort, heapSort, stdSort
    };
    std::vector<std::string> names = {
        "bubble", "insertion", "merge", "quick", "heap", "std::sort"
    };

    for (size_t i = 0; i < fns.size(); ++i) {
        std::vector<int> v = original;
        fns[i](v);
        bool ok = std::is_sorted(v.begin(), v.end());
        std::cout << names[i] << ": " << (ok ? "OK" : "FAIL") << " -> ";
        for (int x : v) std::cout << x << " ";
        std::cout << "\n";
        assert(ok);
    }
    return 0;
}

Output yang Dihasilkan:

text
bubble: OK -> 0 1 2 3 4 5 6 7 8 9
insertion: OK -> 0 1 2 3 4 5 6 7 8 9
merge: OK -> 0 1 2 3 4 5 6 7 8 9
quick: OK -> 0 1 2 3 4 5 6 7 8 9
heap: OK -> 0 1 2 3 4 5 6 7 8 9
std::sort: OK -> 0 1 2 3 4 5 6 7 8 9

Bedah Baris Penting #

bool swapped di bubble sort: flag ini mengaktifkan early exit bila satu pass tidak ada pertukaran — artinya array sudah terurut. Tanpa flag, bubble sort tetap O(n²) bahkan pada data sorted.
buf(v.size()) di merge sort: buffer dialokasikan satu kali di entry point mergeSort, bukan di setiap panggilan rekursif. Ini menghindari overhead alokasi yang berkali-kali.
int pivot = v[hi] di quick sort: pivot terakhir sengaja dipilih untuk memperlihatkan worst-case pada data sorted. Produksi nyata memakai median-of-three atau random pivot untuk menghindari jebakan ini.
int l = 2*i + 1, r = 2*i + 2 di heapify: rumus standar untuk array-based binary heap. Anak kiri node i berada di 2i+1, anak kanan di 2i+2.
assert(ok) di main: program berhenti seketika bila ada algoritma yang gagal. Lebih baik crash awal daripada menjalankan benchmark pada algoritma yang rusak.

Kompilasi dan Pengujian #

bash
g++ -std=c++17 -O2 -Wall -Wextra -o sort_impl.bin sort_impl.cpp
./sort_impl.bin

Pastikan semua algoritma mencetak OK. Pada Bagian 3 kita membungkus keenam fungsi ini dalam harness pengukuran waktu.