Penjelasan bubble sort: cara kerja, kode, dan kompleksitas

Ide dasar dengan kata-kata sederhana

Bandingkan dua elemen pertama. Jika yang pertama lebih besar, tukar. Lalu bandingkan elemen kedua dan ketiga, lalu ketiga dan keempat, dan seterusnya sampai akhir list. Ini satu pass. Setelah pass pertama, elemen terbesar dijamin berada di posisi terakhir, karena setiap perbandingan membawanya satu langkah ke kanan.

Ulangi pass pada bagian yang belum terurut, yang mengecil satu elemen setiap kali. Jika satu pass penuh tidak melakukan pertukaran, list sudah terurut dan Anda bisa berhenti lebih awal.

Contoh pass demi pass

Urutkan [5, 1, 4, 2, 8] secara menaik. Elemen setelah garis berada di posisi akhirnya.

Tanpa keluar lebih awal, algoritma akan menjalankan pass keempat. Dengan itu, tiga pass sudah cukup di sini.

Implementasi Python

def bubble_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    n = len(items)
    for end in range(n - 1, 0, -1):     # last index of the unsorted part
        swapped = False
        for i in range(end):
            if items[i] > items[i + 1]:  # strict >, keeps equal items in order
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:                  # no swaps: already sorted
            break
    return items
print(bubble_sort([5, 1, 4, 2, 8]))     # [1, 2, 4, 5, 8]
print(bubble_sort([3, 3, 1]))           # [1, 3, 3]
print(bubble_sort([]))                  # []

Perulangan dalam berhenti di end karena semua yang setelahnya sudah di tempatnya. Flag swapped memberikan kasus terbaik O(n) pada input yang sudah terurut.

Kompleksitas waktu dan ruang

Untuk 10.000 elemen dengan urutan terbalik, itu hampir 50 juta perbandingan dan pertukaran. Jumlah pertukaran selalu sama dengan jumlah inversi, yaitu pasangan elemen yang urutannya salah.

Perbandingan bubble sort dengan sort lain

Bubble sort stabil karena hanya menukar elemen bersebelahan dan hanya ketika urutannya benar-benar salah, sehingga elemen yang sama tidak pernah saling melewati. Insertion sort punya kompleksitas dan stabilitas yang sama, tetapi dalam praktik melakukan lebih sedikit penulisan dan lebih cepat, itulah sebabnya insertion sort, bukan bubble sort, dipakai di dalam algoritma hibrida seperti Timsort.

Varian dan kesalahan umum

• Cocktail shaker sort berjalan dari kiri ke kanan lalu dari kanan ke kiri secara bergantian, sehingga elemen kecil di ujung (disebut turtle) pindah ke depan lebih cepat. Kompleksitasnya tetap O(n²).
• Comb sort membandingkan elemen yang berjarak tertentu (gap) lalu memperkecil gap, yang menyingkirkan banyak turtle sejak awal; dengan gap 1 algoritma ini menjadi bubble sort.
• Odd-even transposition sort membandingkan semua pasangan ganjil, lalu semua pasangan genap, dan dipakai untuk mengajarkan pengurutan paralel.

Kapan memakai bubble sort

Hampir tidak pernah di kode produksi. Di Python, panggil sorted(items) atau items.sort(), yang memakai Timsort, berjalan dalam O(n log n), dan stabil. Bubble sort tetap berguna untuk diketahui karena paling sederhana dijelaskan, pembuktian kebenarannya mudah diikuti, dan ini pertanyaan pertama yang umum di wawancara atau ujian tentang perulangan, pertukaran, dan kompleksitas.

Satu-satunya keuntungan praktis adalah mendeteksi list yang sudah terurut dalam satu pass O(n), tetapi perulangan biasa yang membandingkan tetangga juga bisa melakukannya tanpa mengurutkan apa pun.