Bubble Sort trong Python là gì? Giải thích với ví dụ

Bubble sort (sắp xếp nổi bọt) là thuật toán sắp xếp để sắp xếp list theo thứ tự tăng dần (hoặc giảm dần). Đây là thuật toán sắp xếp dễ hiểu nhất nhưng không hiệu quả lắm. Có thể dùng cho kích thước đầu vào nhỏ nhưng không hiệu quả về thời gian cho list/mảng lớn. Độ phức tạp thời gian là O(n²). Tuy nhiên, đây là thuật toán sắp xếp tại chỗ (in-place), nghĩa là không dùng thêm không gian phụ. Do đó, hiệu quả về độ phức tạp không gian. Tuy nhiên, ít dùng vì có thuật toán sắp xếp tốt hơn bubble sort.

Bubble Sort hoạt động như thế nào?

Trong bubble sort, dùng hai vòng lặp for. Vòng lặp ngoài duyệt qua list. Vòng lặp trong cũng duyệt qua list cho tất cả các lần lặp của vòng ngoài.

Phép toán chính trong Bubble sort là so sánh hai phần tử liên tiếp. Nếu phần tử đầu lớn hơn phần tử sau, hoán đổi cả hai, để phần tử nhỏ hơn lên trước và phần tử lớn hơn lùi sau. Sau một lần lặp của vòng ngoài, phần tử lớn nhất của list đi đến chỉ số cuối. Sau lần lặp thứ hai của vòng ngoài, phần tử lớn thứ hai đi đến chỉ số倒数第二 và cứ thế. Do đó, ta được list đã sắp xếp sau tất cả các lần lặp.

Hiểu rõ hơn qua ví dụ sau.

Ví dụ

Cần sắp xếp list sau:

Vòng ngoài = 1

5 > 2, do đó hoán đổi cả hai.

5 > 1, do đó hoán đổi cả hai.

5 > 3, do đó hoán đổi cả hai.

5 > 4, do đó hoán đổi cả hai.

(Phần tử lớn nhất 5 đã đến chỉ số cuối sau lần lặp ngoài đầu tiên)

Vòng ngoài = 2

2 > 1, do đó hoán đổi.

Không cần hoán đổi.

Không cần hoán đổi.

Như thấy list đã sắp xếp ở lần lặp ngoài thứ 2. Nhưng vòng ngoài vẫn lặp 3 lần nữa không có hoán đổi. Do đó, chỉ hiện 2 lần lặp trong ví dụ. Đôi khi list sắp xếp ở lần lặp đầu. Đôi khi list sắp xếp ở lần lặp cuối. Do đó, vòng ngoài luôn lặp n lần.

Ví dụ mã

def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-1):
            if arr[j] > arr[j+1]:
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
    return arr

array = [2, 3, 1, 5, 4]
print(bubble_sort(array))

Kết quả

[1, 2, 3, 4, 5]