Thuật toán sắp xếp nổi bọt: cách hoạt động, mã và độ phức tạp

Ý tưởng bằng lời đơn giản

So sánh hai phần tử đầu tiên. Nếu phần tử đầu lớn hơn, đổi chỗ chúng. Rồi so sánh phần tử thứ hai và thứ ba, rồi thứ ba và thứ tư, cứ thế đến cuối danh sách. Đó là một lượt. Sau lượt đầu tiên, phần tử lớn nhất chắc chắn nằm cuối, vì mỗi phép so sánh đẩy nó sang phải một bước.

Lặp lại lượt này trên phần chưa sắp xếp, vốn thu nhỏ đi một phần tử mỗi lần. Nếu cả một lượt không có lần đổi chỗ nào, danh sách đã sắp xếp và bạn có thể dừng sớm.

Ví dụ minh họa từng lượt

Sắp xếp [5, 1, 4, 2, 8] theo thứ tự tăng dần. Các phần tử sau dấu gạch đã ở vị trí cuối cùng.

Nếu không thoát sớm, thuật toán sẽ chạy lượt thứ tư. Khi có thoát sớm, ba lượt là đủ trong ví dụ này.

Cài đặt bằng 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([]))                  # []

Vòng lặp trong dừng ở end vì mọi thứ phía sau đã đúng chỗ. Cờ swapped cho trường hợp tốt nhất O(n) với đầu vào đã sắp xếp.

Độ phức tạp thời gian và không gian

Với 10.000 phần tử theo thứ tự ngược, đó là gần 50 triệu phép so sánh và đổi chỗ. Số lần đổi chỗ luôn bằng số nghịch thế (inversion), tức số cặp phần tử sai thứ tự.

So sánh sắp xếp nổi bọt với các thuật toán khác

Sắp xếp nổi bọt ổn định vì nó chỉ đổi chỗ các phần tử kề nhau và chỉ khi chúng thực sự sai thứ tự, nên các phần tử bằng nhau không bao giờ vượt qua nhau. Sắp xếp chèn có cùng độ phức tạp và tính ổn định nhưng trong thực tế ghi ít hơn và nhanh hơn, vì thế nó, chứ không phải sắp xếp nổi bọt, được dùng trong các thuật toán lai như Timsort.

Biến thể và lỗi thường gặp

• Cocktail shaker sort đi từ trái sang phải rồi từ phải sang trái ở các lượt xen kẽ, giúp các phần tử nhỏ nằm cuối (gọi là “rùa”) tiến lên đầu nhanh hơn. Nó vẫn là O(n²).
• Comb sort so sánh các phần tử cách nhau một khoảng (gap) và thu nhỏ dần khoảng đó, loại bỏ nhiều “rùa” từ sớm; khi gap bằng 1 nó trở thành sắp xếp nổi bọt.
• Odd-even transposition sort so sánh mọi cặp lẻ rồi mọi cặp chẵn, và được dùng để dạy sắp xếp song song.

Khi nào nên dùng sắp xếp nổi bọt

Gần như không bao giờ trong mã sản phẩm. Trong Python, hãy gọi sorted(items) hoặc items.sort(), dùng Timsort, chạy O(n log n) và ổn định. Sắp xếp nổi bọt vẫn đáng biết vì nó là thuật toán sắp xếp dễ giải thích nhất, chứng minh tính đúng đắn dễ theo dõi, và là câu hỏi đầu tiên quen thuộc trong phỏng vấn hay đề thi về vòng lặp, đổi chỗ và độ phức tạp.

Ưu điểm thực tế duy nhất là phát hiện danh sách đã sắp xếp chỉ trong một lượt O(n), nhưng một vòng lặp thường so sánh các phần tử kề nhau cũng làm được mà không cần sắp xếp gì.