Membandingkan Algoritma Sorting: Kapan Menggunakan Bubble, Merge, dan Quick Sort?

Pendahuluan

Sorting atau pengurutan data adalah operasi yang hampir selalu muncul dalam pengembangan perangkat lunak — mulai dari menampilkan daftar produk berdasarkan harga, hingga memproses log server secara efisien. Masalahnya, ada puluhan algoritma sorting yang tersedia, dan memilih yang tepat bisa memberi dampak besar pada performa aplikasi.

Artikel ini fokus pada tiga algoritma sorting paling sering dipelajari: Bubble Sort, Merge Sort, dan Quick Sort. Kita tidak hanya akan melihat cara kerjanya, tapi — yang lebih penting — kapan dan mengapa kamu harus (atau tidak harus) memilih masing-masing.

Asumsi: kamu sudah paham konsep dasar loop, array, dan rekursi. Kita juga akan sedikit menyentuh kompleksitas waktu (O notation), tapi fokus utama adalah pertimbangan praktis.

Bubble Sort: Kesederhanaan dan Kapan Digunakan

Cara Kerja

Bubble Sort bekerja dengan membandingkan dua elemen berdekatan secara berulang, lalu menukarnya jika urutannya salah. Proses ini diulang sampai tidak ada lagi pertukaran yang dibutuhkan.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # Optimasi: hentikan lebih awal jika sudah terurut
        if not swapped:
            break
    return arr

# Contoh penggunaan
data = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(data))
# Output: [11, 12, 22, 25, 34, 64, 90]

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

console.log(bubbleSort([64, 34, 25, 12, 22, 11, 90]));
// Output: [11, 12, 22, 25, 34, 64, 90]

Kompleksitas

Space complexity: O(1) — in-place, tidak butuh memori tambahan.

Kapan Menggunakan Bubble Sort?

Jujur saja: hampir tidak pernah di production untuk data berukuran besar. Tapi ada skenario sah:

• Dataset sangat kecil (< 10 elemen): overhead algoritma kompleks tidak sepadan.
• Data hampir terurut: dengan optimasi swapped, Bubble Sort bisa O(n) jika hanya 1-2 elemen yang salah posisi.
• Konteks edukasi atau debugging cepat: kodenya mudah ditulis dan dipahami dalam hitungan menit.
• Embedded system dengan memori sangat terbatas: tidak butuh stack rekursi atau array tambahan.

Hindari Bubble Sort untuk array dengan ribuan elemen atau lebih — performanya akan jauh lebih lambat dibanding alternatif lain.

Merge Sort: Stabilitas dan Kinerja Konsisten

Cara Kerja

Merge Sort menggunakan strategi divide and conquer: bagi array menjadi dua bagian, urutkan masing-masing secara rekursif, lalu gabungkan (merge) hasilnya.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Contoh penggunaan
data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data))
# Output: [3, 9, 10, 27, 38, 43, 82]

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return [...result, ...left.slice(i), ...right.slice(j)];
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// Output: [3, 9, 10, 27, 38, 43, 82]

Kompleksitas

Space complexity: O(n) — membutuhkan array tambahan untuk proses merge.

Keunggulan Kunci: Stabilitas

Merge Sort adalah stable sort: elemen dengan nilai sama mempertahankan urutan relatifnya dari array asli. Ini krusial saat kamu mengurutkan objek berdasarkan lebih dari satu kriteria.

# Contoh: urutkan transaksi berdasarkan jumlah, pertahankan urutan waktu
transactions = [
    {"id": 1, "amount": 100, "time": "10:00"},
    {"id": 2, "amount": 50,  "time": "10:05"},
    {"id": 3, "amount": 100, "time": "10:10"},
    {"id": 4, "amount": 50,  "time": "10:15"},
]

# Dengan stable sort, transaksi id=1 selalu sebelum id=3 (sama-sama amount 100)
sorted_transactions = merge_sort_by_amount(transactions)
# Hasilnya: id=2 (50, 10:05), id=4 (50, 10:15), id=1 (100, 10:00), id=3 (100, 10:10)

Kapan Menggunakan Merge Sort?

• Data dalam jumlah besar dengan kebutuhan performa yang dapat diprediksi (O(n log n) di semua kasus).
• Sorting data eksternal (file besar yang tidak muat di RAM): Merge Sort sangat cocok karena pola aksesnya sekuensial.
• Butuh stable sort: saat urutan relatif elemen yang sama harus dipertahankan.
• Linked list: Merge Sort lebih efisien di linked list dibanding Quick Sort karena tidak butuh random access.

Perhatikan kebutuhan memori tambahan O(n). Untuk dataset yang sangat besar di lingkungan terbatas memori, ini bisa jadi masalah.

Quick Sort: Kecepatan Rata-Rata Terbaik

Cara Kerja

Quick Sort memilih satu elemen sebagai pivot, lalu mempartisi array sehingga semua elemen lebih kecil dari pivot berada di kiri, dan yang lebih besar berada di kanan. Proses ini diulang secara rekursif.

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1

    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)

    return arr

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Contoh penggunaan
data = [10, 7, 8, 9, 1, 5]
print(quick_sort(data))
# Output: [1, 5, 7, 8, 9, 10]

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

console.log(quickSort([10, 7, 8, 9, 1, 5]));
// Output: [1, 5, 7, 8, 9, 10]

Kompleksitas

Space complexity: O(log n) rata-rata (stack rekursi).

Kenapa Lebih Cepat dari Merge Sort dalam Praktik?

Meski kompleksitas rata-ratanya sama O(n log n), Quick Sort biasanya lebih cepat di dunia nyata karena:

1. Cache-friendly: mengakses memori secara lokal (in-place), sehingga lebih efisien di CPU cache.
2. Konstanta lebih kecil: operasi per elemen lebih sedikit dibanding Merge Sort.

Kasus terburuk O(n²) terjadi saat pivot selalu dipilih dari elemen terkecil/terbesar (misal array sudah terurut). Solusinya: gunakan randomized pivot atau median-of-three.

import random

def quick_sort_random(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        # Pilih pivot acak untuk menghindari kasus terburuk
        rand_idx = random.randint(low, high)
        arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
        pivot_index = partition(arr, low, high)
        quick_sort_random(arr, low, pivot_index - 1)
        quick_sort_random(arr, pivot_index + 1, high)
    return arr

Kapan Menggunakan Quick Sort?

• General-purpose sorting untuk array besar di memori: ini pilihan default kebanyakan library standar.
• Tidak butuh stable sort: jika urutan relatif elemen sama tidak penting.
• Memori terbatas: lebih hemat memori dibanding Merge Sort.
• Data random atau tidak terprediksi: dengan randomized pivot, kasus terburuk praktis tidak terjadi.

Contoh Kasus Nyata: Kapan Memilih yang Mana?

Kasus 1: Leaderboard Game Online

Kamu perlu mengurutkan 1 juta pemain berdasarkan skor secara real-time.

Pilihan: Quick Sort (atau built-in sort)

Performa rata-rata terbaik, tidak perlu stable sort karena skor unik per pemain, dan hemat memori.

players = [{"name": "Andi", "score": 4200}, {"name": "Budi", "score": 3800}, ...]
players.sort(key=lambda x: x["score"], reverse=True)  # Python's built-in (Timsort)

Python’s built-in sort() menggunakan Timsort — kombinasi Merge Sort dan Insertion Sort — yang optimal untuk data dunia nyata.

Kasus 2: Sistem Rekonsiliasi Keuangan

Kamu mengurutkan 500.000 transaksi berdasarkan nominal, lalu berdasarkan waktu untuk yang nominalnya sama.

Pilihan: Merge Sort (atau stable sort)

Stabilitas sangat penting di sini — urutan transaksi dengan nominal sama harus tetap berdasarkan waktu masuk.

from functools import cmp_to_key

transactions = [
    {"id": 1, "amount": 100, "timestamp": 1700000001},
    {"id": 2, "amount": 100, "timestamp": 1700000002},
    # ...
]

# Python's sorted() adalah stable sort
sorted_tx = sorted(transactions, key=lambda x: x["amount"])
# Transaksi dengan amount sama tetap dalam urutan timestamp aslinya

Kasus 3: Validasi Form dengan Beberapa Pilihan

Kamu perlu mengurutkan 5 opsi dropdown yang dipilih pengguna.

Pilihan: Bubble Sort atau bahkan built-in

Untuk 5 elemen, semua algoritma praktis sama cepatnya. Tulis kode paling sederhana.

Ringkasan Perbandingan

*Bisa dihindari dengan randomized pivot.

Kesimpulan

Memilih algoritma sorting bukan soal mana yang “paling canggih”, tapi soal mana yang paling sesuai dengan kebutuhan spesifikmu:

• Bubble Sort: simpel, cocok untuk data kecil atau hampir terurut. Jangan dipakai untuk data besar.
• Merge Sort: pilih ini saat kamu butuh stabilitas dan performa yang dapat diprediksi — terutama untuk data eksternal atau sorting multi-kriteria.
• Quick Sort: pilihan default untuk performa umum terbaik di data besar dalam memori. Gunakan randomized pivot untuk menghindari kasus terburuk.

Dalam praktik sehari-hari, library standar sudah mengimplementasikan algoritma yang dioptimalkan (Python menggunakan Timsort, Java menggunakan dual-pivot Quicksort untuk primitif dan Timsort untuk objek). Memahami cara kerja algoritma di baliknya membuatmu bisa memilih pendekatan yang tepat dan men-debug masalah performa dengan lebih efektif.