Bubble Sort membandingkan elemen berpasangan dan menukar jika urutannya salah. Elemen terbesar "menggelembung" ke akhir.

Kompleksitas: O(n²) — lambat tapi mudah dipahami

Cara kerja:

1. Bandingkan elemen ke-i dengan ke-(i+1)
2. Jika salah urutan, tukar
3. Ulangi sampai tidak ada lagi pertukaran

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // Sudah terurut!
  }
  return arr;
}

bubbleSort([64, 34, 25, 12, 22, 11, 90]);
// Pass 1: [34, 25, 12, 22, 11, 64, 90]
// Pass 2: [25, 12, 22, 11, 34, 64, 90]
// ... sampai terurut
// Hasil: [11, 12, 22, 25, 34, 64, 90]

Optimasi: Flag swapped menghentikan loop lebih awal jika sudah terurut → best case O(n).

Kelebihan:

• Sangat mudah dipahami dan diimplementasi
• Stabil (elemen equal tidak berpindah posisi relatif)

Kekurangan:

• O(n²) — sangat lambat untuk data besar
• Hampir tidak pernah dipakai di production

Bubble Sort adalah alat belajar yang bagus, tapi di dunia nyata gunakan Merge Sort atau Quick Sort.

🎭 Analogi sehari-hari: Bayangin baris anak SD diurutin tinggi badan. Cara bubble sort: tiap pasangan bersebelahan dibandingin, yang lebih tinggi tukar ke kanan. Loop terus sampai gak ada lagi yang nukar. Anak paling tinggi menggelembung ke kanan setiap putaran (makanya "bubble").

💡 Mengapa Bubble Sort dipelajari padahal lambat? Karena ini sort paling gampang dijelasin + perfect untuk belajar konsep stable sort, swap, dan optimization (early exit). Foundation conceptual untuk algoritma sort lain.

⚠️ Jebakan umum:

• Lupa flag swapped — best case tetap O(n²) tanpa optimization
• Pakai di production untuk n besar = aplikasi hang/lambat
• Inner loop sampai n-1 padahal cukup n-1-i (sisa belakang sudah sorted)
• Salah comparator — descending vs ascending tertukar = data gak ke-sort dengan benar

🎯 Karakter Bubble Sort:

• In-place: O(1) extra memory (bagus)
• Stable: ya (elemen sama urutan tidak berubah)
• Best: O(n) — sudah sorted, 1 pass cek aja
• Average/Worst: O(n²)
• Adaptive: ya — lebih cepat untuk hampir-sorted

🧪 Tebakan cepat: Sort [5, 1, 4, 2, 8]. Pass 1: [1,4,2,5,8]. Pass 2: [1,2,4,5,8]. Pass 3: tidak ada swap → done. 3 pass untuk 5 elemen. Walau O(n²) worst, aktualnya tergantung data.

TL;DR: Bubble Sort = compare-swap pasangan tetangga, loop sampai sorted. O(n²) worst, O(n) best dengan early exit. Belajar konsep stable sort, jangan dipakai di production.