Bubble Sort

Bubble sort adalah algoritma sorting paling sederhana yang berkerja dengan membandingkan setiap pasangan elemen bertetangga dan menukarnya bila urutan salah. Algoritma ini mendapat namanya dari cara elemen bernilai besar “menggelembung” naik ke akhir array seperti gelembung udara. Meski tidak efisien untuk data besar, bubble sort sangat baik sebagai pengantar karena logikanya transparan. Pada Chapter ini kita akan membedah mekanisme bubble sort, mengimplementasikannya dalam C++, dan menambahkan optimasi early termination yang membuatnya adaptif terhadap data hampir terurut. Pada akhir chapter kita akan tahu kapan bubble sort layak dipakai dan kapan harus dihindari.

Aturan: Bandingkan dan Tukar Tetangga #

Bubble sort melakukan n-1 pass. Pada pass ke-i, algoritma membandingkan setiap pasangan v[j] dan v[j+1] untuk j = 0, 1, ..., n-i-2. Bila v[j] > v[j+1], kedua elemen ditukar. Setelah pass ke-i selesai, i+1 elemen terbesar sudah berada di posisi yang benar pada bagian akhir array.

Mekanisme Kerja #

Setelah satu pass penuh, elemen terbesar “menggelembung” ke indeks n-1. Setelah pass kedua, elemen terbesar kedua berada di indeks n-2. Demikian seterusnya. Setelah n-1 pass, seluruh array terurut.

Pada array {5, 2, 9, 1, 5, 6}, pass pertama bekerja sebagai berikut:

[5, 2, 9, 1, 5, 6]
   ^--- bandingkan 5,2 -> swap -> [2, 5, 9, 1, 5, 6]
       ^--- bandingkan 5,9 -> OK
           ^--- bandingkan 9,1 -> swap -> [2, 5, 1, 9, 5, 6]
               ^--- bandingkan 9,5 -> swap -> [2, 5, 1, 5, 9, 6]
                   ^--- bandingkan 9,6 -> swap -> [2, 5, 1, 5, 6, 9]
                                                   ^--- elemen 9 di tempat final

Kode: Bubble Sort Naif #

#include <iostream>
#include <vector>
#include <utility>

void bubble_sort_naive(std::vector<int>& v) {
    int n = static_cast<int>(v.size());
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (v[j] > v[j + 1]) std::swap(v[j], v[j + 1]);
        }
    }
}

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

int main() {
    std::vector<int> a = {5, 2, 9, 1, 5, 6};
    bubble_sort_naive(a);
    std::cout << "Naive:   "; print(a);
    return 0;
}

Output yang Dihasilkan:

Naive:    1 2 5 5 6 9

Bedah Kode Baris-per-Baris #

1. int n = static_cast<int>(v.size());: menyimpan ukuran array dalam variabel lokal n agar tidak memanggil v.size() berulang pada loop.
2. for (int i = 0; i < n - 1; ++i): loop luar untuk pass. Total n - 1 pass.
3. for (int j = 0; j < n - i - 1; ++j): loop dalam membandingkan pasangan bertetangga. Batas atas n - i - 1 karena i elemen terbesar sudah berada di posisi benar pada bagian akhir.
4. if (v[j] > v[j + 1]) std::swap(v[j], v[j + 1]);: tukar bila urutan salah. std::swap dari <utility> melakukan pertukaran efisien.
5. Kompleksitas: baik best, average, dan worst adalah O(n²) karena algoritma selalu melakukan semua pass terlepas dari kondisi input.

Optimasi: Early Termination #

Pada data hampir terurut, banyak pass tidak melakukan pertukaran apa pun. Kita dapat mendeteksi keadaan ini dengan flag tukar. Bila satu pass penuh tidak ada pertukaran, array sudah terurut dan algoritma dapat berhenti lebih awal.

Kode: Bubble Sort Adaptif #

#include <iostream>
#include <vector>
#include <utility>

void bubble_sort_adaptive(std::vector<int>& v, int& passes, int& swaps) {
    int n = static_cast<int>(v.size());
    passes = 0;
    swaps = 0;
    for (int i = 0; i < n - 1; ++i) {
        bool tukar = false;
        ++passes;
        for (int j = 0; j < n - i - 1; ++j) {
            if (v[j] > v[j + 1]) {
                std::swap(v[j], v[j + 1]);
                tukar = true;
                ++swaps;
            }
        }
        if (!tukar) break;
    }
}

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

int main() {
    std::vector<int> b = {1, 2, 3, 5, 4, 6, 7};
    int passes, swaps;
    bubble_sort_adaptive(b, passes, swaps);
    std::cout << "Adaptive: "; print(b);
    std::cout << "  passes=" << passes << ", swaps=" << swaps << '\n';

    std::vector<int> c = {1, 2, 3, 4, 5, 6, 7};
    bubble_sort_adaptive(c, passes, swaps);
    std::cout << "Adaptive (sorted): "; print(c);
    std::cout << "  passes=" << passes << ", swaps=" << swaps << '\n';

    return 0;
}

Output yang Dihasilkan:

Adaptive:  1 2 3 4 5 6 7
  passes=2, swaps=1
Adaptive (sorted):  1 2 3 4 5 6 7
  passes=1, swaps=0

Bedah Kode Baris-per-Baris #

1. bool tukar = false;: flag untuk mendeteksi apakah ada pertukaran dalam satu pass.
2. ++passes;: penghitung pass untuk verifikasi. Variabel ini dilewatkan oleh referensi ke pemanggil.
3. if (!tukar) break;: bila tidak ada pertukaran dalam satu pass penuh, array sudah terurut. Loop luar keluar lebih awal.
4. Output {1, 2, 3, 5, 4, 6, 7}: hanya butuh 2 pass dan 1 swap. Bandingkan dengan versi naif yang selalu melakukan n-1 = 6 pass.
5. Output {1, 2, 3, 4, 5, 6, 7}: hanya 1 pass dengan 0 swap. Kompleksitas best case O(n).

Kompleksitas #

Stabilitas #

Bubble sort stabil. Pertukaran hanya terjadi bila v[j] > v[j+1] (strict greater). Elemen yang equal tidak pernah ditukar, sehingga urutan relatif antar elemen equal tetap dipertahankan.

Kapan Bubble Sort Layak Dipakai #

• n sangat kecil (misalnya < 16) — konstanta kecil dan kode sederhana.
• Data hampir terurut — bubble sort adaptif menjadi O(n).
• Pembelajaran — algoritma paling transparan untuk mengenalkan sorting.

Pembanding dengan std::sort #

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

int main() {
    const int N = 5000;
    std::vector<int> a(N);
    for (int i = 0; i < N; ++i) a[i] = (i * 37 + 11) % 1000;

    auto b = a;
    auto t1 = std::chrono::high_resolution_clock::now();
    std::sort(b.begin(), b.end());
    auto t2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> d_std = t2 - t1;

    // bubble sort naif
    auto c = a;
    t1 = std::chrono::high_resolution_clock::now();
    int n = static_cast<int>(c.size());
    for (int i = 0; i < n - 1; ++i)
        for (int j = 0; j < n - i - 1; ++j)
            if (c[j] > c[j + 1]) std::swap(c[j], c[j + 1]);
    t2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> d_bub = t2 - t1;

    std::cout << "std::sort   : " << d_std.count() << " ms\n";
    std::cout << "bubble sort : " << d_bub.count() << " ms\n";
    std::cout << "sorted sama : " << (b == c ? "ya" : "tidak") << '\n';
    return 0;
}

Output yang Dihasilkan (waktu bervariasi antar mesin):

std::sort   : 0.2 ms
bubble sort : 40 ms
sorted sama : ya

1. std::sort memakai introsort (hybrid quick + heap + insertion) dengan kompleksitas O(n log n).
2. Bubble sort naif membutuhkan n²/2 ≈ 1,25×10⁷ pembandingan pada N=5000, jauh lebih lambat daripada n log n ≈ 6×10⁴ milik std::sort.
3. Output: std::sort ~200× lebih cepat daripada bubble sort pada ukuran ini.

Ringkasan #

• Bubble sort membandingkan pasangan bertetangga dan menukar bila urutan salah.
• Versi naif selalu O(n²); versi adaptif (dengan early termination) bisa O(n) pada data hampir terurut.
• Bubble sort stabil dan in-place (O(1) memori tambahan).
• Layak dipakai hanya untuk n kecil atau data hampir terurut; untuk data besar, gunakan std::sort.

Bubble sort menjadi dasar konseptual untuk memahami selection sort dan insertion sort yang akan kita bahas pada chapter berikutnya.