Bubble sort adalah algoritma sorting paling sederhana yang sering dipakai sebagai pengantar konsep sorting. Algoritma ini bekerja dengan membandingkan setiap pasangan elemen berdekatan dan menukarnya bila urutan salah. Walaupun kompleksitasnya O(n^2)—jauh lebih lambat dibanding algoritma modern seperti merge sort—bubble sort punya keunggulan: implementasi sangat sederhana dan stabil. Pada chapter ini kita akan mengimplementasikan versi naive, versi optimized dengan early exit, lalu menghitung pass dan pertukaran untuk berbagai skenario data.

Cara Kerja Bubble Sort #

Pada setiap pass, algoritma menelusuri array dari kiri ke kanan, membandingkan elemen a[j] dan a[j+1]. Bila a[j] > a[j+1], keduanya ditukar. Setelah satu pass, elemen terbesar akan “menggelembung” ke posisi paling kanan. Algoritma mengulang pass ini hingga n-1 kali. Kompleksitas waktu O(n^2) muncul dari loop bersarang n x n.

Optimisasi penting: bila satu pass tidak menghasilkan pertukaran apapun, array sudah terurut dan algoritma boleh berhenti lebih awal. Pada kasus data yang sudah hampir terurut, optimisasi ini menurunkan kompleksitas praktis menjadi O(n).

Versi Naive dan Optimized #

Kita akan menulis dua versi bubble sort untuk membandingkan keduanya.

c 
#include <stdio.h>

/* Bubble sort naive: selalu n-1 pass */
void bubble_naive(int *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
            }
        }
    }
}

/* Bubble sort optimized dengan early exit */
void bubble_optimized(int *a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int ditukar = 0;
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                ditukar = 1;
            }
        }
        if (!ditukar) break;  /* tidak ada pertukaran -> sudah terurut */
    }
}

static void cetak(const int *a, int n, const char *label) {
    printf("%s: ", label);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
}

int main(void) {
    int a[] = {5, 1, 4, 2, 8, 3, 7, 6};
    int n = sizeof(a) / sizeof(a[0]);
    cetak(a, n, "Sebelum");
    bubble_naive(a, n);
    cetak(a, n, "Naive  ");

    int b[] = {5, 1, 4, 2, 8, 3, 7, 6};
    bubble_optimized(b, n);
    cetak(b, n, "Optimiz");

    /* Kasus sudah terurut */
    int c[] = {1, 2, 3, 4, 5};
    int m = 5;
    bubble_optimized(c, m);
    cetak(c, m, "Terurut");

    return 0;
}

Output yang Dihasilkan:

text 
Sebelum: 5 1 4 2 8 3 7 6 
Naive  : 1 2 3 4 5 6 7 8 
Optimiz: 1 2 3 4 5 6 7 8 
Terurut: 1 2 3 4 5

Kedua versi menghasilkan array terurut. Perbedaan utama adalah behavior pada data yang sudah terurut: versi optimized berhenti setelah 1 pass, sedangkan versi naive tetap menjalankan n-1 pass sia-sia.

Mari kita telaah baris-baris kode di atas:

  1. Baris 4-11 (bubble_naive): dua loop bersarang. Loop luar i dari 0 sampai n-2 (total n-1 pass). Loop dalam j dari 0 sampai n-i-2 (membandingkan elemen berdekatan). Setiap pasangan yang urutannya salah ditukar dengan trik variabel sementara t.
  2. Baris 14-26 (bubble_optimized): struktur sama dengan naive, ditambah flag ditukar. Flag direset ke 0 di awal setiap pass lalu di-set 1 bila ada pertukaran. Bila setelah pass selesai ditukar masih 0, array sudah terurut—break keluar dari loop luar.
  3. Baris 24 (if (!ditukar) break;): inti optimisasi. Trik ini menurunkan best case dari O(n^2) menjadi O(n).
  4. Baris 28-32 (cetak): helper untuk mencetak array dengan label, mempermudah verifikasi.
  5. Baris 38-39 (int b[] = {...}; bubble_optimized(b, n);): salinan data untuk versi optimized karena bubble_naive sudah memodifikasi a di tempat.

Menghitung Jumlah Pass dan Pertukaran #

Untuk memahami kapan optimisasi membantu, kita akan menghitung jumlah pass dan pertukaran pada tiga skenario: data acak, data terurut, dan data terbalik.

c 
#include <stdio.h>

/* Bubble sort dengan penghitung pass dan pertukaran */
void bubble_count(int *a, int n, int *jumlah_pass, int *jumlah_tukar) {
    *jumlah_pass = 0;
    *jumlah_tukar = 0;
    for (int i = 0; i < n - 1; i++) {
        int ditukar = 0;
        (*jumlah_pass)++;
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                ditukar = 1;
                (*jumlah_tukar)++;
            }
        }
        if (!ditukar) break;
    }
}

int main(void) {
    int a[] = {5, 1, 4, 2, 8, 3, 7, 6};
    int b[] = {1, 2, 3, 4, 5};
    int c[] = {5, 4, 3, 2, 1};
    int n = 5;

    int pass, tukar;

    bubble_count(a, 8, &pass, &tukar);
    printf("Acak    (8 elemen): pass=%d, tukar=%d\n", pass, tukar);

    bubble_count(b, n, &pass, &tukar);
    printf("Terurut (5 elemen): pass=%d, tukar=%d\n", pass, tukar);

    bubble_count(c, n, &pass, &tukar);
    printf("Terbalik(5 elemen): pass=%d, tukar=%d\n", pass, tukar);

    return 0;
}

Output yang Dihasilkan:

text 
Acak    (8 elemen): pass=4, tukar=10
Terurut (5 elemen): pass=1, tukar=0
Terbalik(5 elemen): pass=4, tukar=10

Hasilnya menggambarkan tiga kelas kompleksitas praktis:

  • Data terurut: 1 pass, 0 pertukaran—algoritma langsung berhenti. Best case O(n).
  • Data acak: jumlah pass lebih sedikit dari n-1 karena pertukaran terjadi. Average case O(n^2).
  • Data terbalik: butuh n-1 pass penuh dengan pertukaran maksimum. Worst case O(n^2) dengan konstanta paling besar.

Kapan Bubble Sort Cocok Dipakai #

Walaupun bubble sort jarang dipakai di produksi, ada situasi di mana algoritma ini masuk akal:

  • Data hampir terurut: optimisasi early exit membuat bubble sort berjalan cepat pada data yang hanya butuh sedikit pertukaran.
  • Ukuran data sangat kecil (n < 50): overhead rendah dan kode sederhana.
  • Stability diperlukan: bubble sort natural stabil tanpa modifikasi.
  • Memori sangat terbatas: bubble sort in-place dengan space complexity O(1).