Bubble sort

Bubble sort membandingkan setiap pasangan data yang bersebelahan dan menukarnya jika salah urutan. Setelah satu putaran, data terbesar "menggelembung" ke posisi paling kanan.

1def bubble_sort(data):2    data = data.copy()3    n = len(data)4    for putaran in range(n - 1):5        ditukar = False6        for i in range(n - 1 - putaran):7            if data[i] > data[i + 1]:8                data[i], data[i + 1] = data[i + 1], data[i]9                ditukar = True10        if not ditukar:11            break12    return data1314print(bubble_sort([5, 1, 4, 2, 8]))15print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))

[1, 2, 4, 5, 8]
[11, 12, 22, 25, 34, 64, 90]

Dua perbaikan kecil pada kode ini:

• range(n - 1 - putaran): setelah setiap putaran, data terbesar sudah di tempatnya, jadi bagian akhir tidak perlu diperiksa lagi.
• ditukar: jika satu putaran penuh tidak ada penukaran, data sudah urut dan perulangan dihentikan.

Analisis

• Terburuk (data terbalik): sekitar n²/2 perbandingan, jadi O(n²).
• Terbaik (data sudah urut): hanya satu putaran, jadi O(n) berkat penanda ditukar.
• Stabil: data yang nilainya sama tidak bertukar posisi.

Bubble sort mudah dipahami, tetapi terlalu lambat untuk data besar. Nilainya ada pada pelajaran tentang cara membandingkan dan menukar.

1def bubble_sort_hitung(data):2    data = data.copy()3    n = len(data)4    banding = tukar = 05    for putaran in range(n - 1):6        ditukar = False7        for i in range(n - 1 - putaran):8            banding += 19            if data[i] > data[i + 1]:10                data[i], data[i + 1] = data[i + 1], data[i]11                tukar += 112                ditukar = True13        if not ditukar:14            break15    return banding, tukar1617print("Sudah urut:", bubble_sort_hitung([1, 2, 3, 4, 5]))18print("Terbalik  :", bubble_sort_hitung([5, 4, 3, 2, 1]))

Sudah urut: (4, 0)
Terbalik  : (10, 10)