0

Thuật toán & CTDL #01: Bubble Sort - thuật toán ai cũng học đầu tiên nhưng gần như không ai dùng thật

Gần như ai học lập trình cũng gặp Bubble Sort đầu tiên. Code ngắn, dễ hiểu, chạy đúng. Nhưng thử đưa cho nó 1 triệu phần tử thì nó cần gần 500 tỷ phép so sánh. Bài này đi qua cách Bubble Sort chạy, đếm chính xác số phép so sánh trên một ví dụ nhỏ, và giải thích vì sao nó gần như chỉ xuất hiện trong giáo trình và phòng phỏng vấn.

Ý tưởng

Luật chỉ có một: so sánh hai phần tử đứng cạnh nhau, nếu bên trái lớn hơn bên phải thì đổi chỗ.

Quét từ trái sang phải một lượt như vậy, phần tử lớn nhất sẽ bị đẩy liên tục về cuối mảng, giống bong bóng nổi lên mặt nước. Hết lượt 1, phần tử lớn nhất đã nằm đúng chỗ. Lượt 2 không cần xét ô cuối nữa, và cứ thế mỗi lượt ngắn đi một ô.

Thêm một cải tiến nhỏ nhưng quan trọng: nếu cả một lượt không có lần đổi chỗ nào, mảng đã được sắp xong và ta dừng luôn.

Chạy tay một ví dụ

Mảng giống trong video: [5, 2, 8, 1, 7, 3, 6, 4], 8 phần tử.

Lượt Số lần so sánh Mảng sau lượt
1 7 [2, 5, 1, 7, 3, 6, 4, 8]
2 6 [2, 1, 5, 3, 6, 4, 7, 8]
3 5 [1, 2, 3, 5, 4, 6, 7, 8]
4 4 [1, 2, 3, 4, 5, 6, 7, 8]
5 3 không đổi chỗ lần nào, dừng

Để ý lượt 1: số 8 gặp ai cũng lớn hơn nên bị đẩy liên tục từ vị trí thứ 3 về cuối mảng. Sau lượt 4 mảng thực ra đã sắp xong, nhưng thuật toán chưa biết điều đó. Nó cần thêm lượt 5 để xác nhận "không có gì để đổi nữa" rồi mới dừng.

Tổng cộng: 7 + 6 + 5 + 4 + 3 = 25 lần so sánh cho 8 phần tử. Nghe thì ít, nhưng hãy xem nó tăng thế nào ở phần độ phức tạp.

Code Python

def bubble_sort(a):
    a = list(a)                      # không sửa mảng gốc
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):   # i ô cuối đã đúng chỗ
            if a[j] > a[j + 1]:      # dùng > chứ không phải >= để giữ stable
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:              # cả lượt không đổi chỗ: đã sắp xong
            break
    return a

print(bubble_sort([5, 2, 8, 1, 7, 3, 6, 4]))  # [1, 2, 3, 4, 5, 6, 7, 8]
print(bubble_sort([]))                        # []

Độ phức tạp

  • Tệ nhất (mảng sắp ngược): mọi lượt đều chạy hết, tổng số so sánh là n(n-1)/2, tức O(n²).
  • Trung bình: vẫn O(n²).
  • Tốt nhất (mảng đã sắp sẵn): lượt đầu không đổi chỗ lần nào, dừng sau n-1 lần so sánh, tức O(n). Lưu ý: kết quả này chỉ đúng khi có cờ swapped. Bản "sách giáo khoa" không có cờ thì luôn là O(n²).
  • Bộ nhớ: O(1), sắp xếp tại chỗ (in-place).
  • Stable: có. Hai phần tử bằng nhau không bao giờ bị đổi chỗ cho nhau, miễn là bạn so sánh bằng >.

Giờ tính cho 1 triệu phần tử: n(n-1)/2 = 10⁶ × (10⁶ - 1) / 2 ≈ 500 tỷ phép so sánh trong trường hợp tệ nhất. Giả sử máy làm được 1 tỷ phép so sánh mỗi giây (rất lạc quan với Python), vẫn mất hơn 8 phút. Với Python thuần thì tính bằng giờ. Trong khi sorted() có sẵn xử lý 1 triệu số trong chưa tới một giây.

Đó là cái giá của O(n²): dữ liệu tăng 10 lần thì thời gian tăng 100 lần.

Khi nào dùng, khi nào không

Thẳng thắn mà nói, trong code production bạn gần như không bao giờ nên tự viết Bubble Sort. Dùng hàm sort của ngôn ngữ.

Nó vẫn có chỗ đứng:

  • Học và dạy: dễ hình dung nhất để hiểu khái niệm "lượt", "đổi chỗ", "stable", "dừng sớm".
  • Kiểm tra mảng gần như đã sắp: một lượt Bubble Sort chính là một lần kiểm tra "đã sắp chưa" kèm sửa các cặp lệch kề nhau.
  • Mảng cực nhỏ, môi trường cực hạn chế (vài phần tử, không có thư viện). Nhưng kể cả lúc đó, Insertion Sort (bài 03) thường là lựa chọn tốt hơn.

Lỗi hay gặp

  1. Quên thu hẹp vòng trong: viết range(n - 1) thay vì range(n - 1 - i). Kết quả vẫn đúng nhưng so sánh thừa với các ô đã đúng chỗ.
  2. Quên cờ swapped: mất luôn trường hợp tốt nhất O(n).
  3. Dùng >=: đổi chỗ cả hai phần tử bằng nhau, thuật toán mất tính stable.
  4. Tràn chỉ số: vòng trong chạy tới n - i rồi truy cập a[j + 1] là IndexError.

Câu hỏi phỏng vấn hay gặp

  • Bubble Sort có stable không? Vì sao? Có, vì chỉ đổi chỗ khi bên trái lớn hơn hẳn.
  • Trường hợp tốt nhất là gì? O(n) với mảng đã sắp, nhưng chỉ khi có cờ dừng sớm.
  • So với Selection Sort thì sao? Cùng O(n²) so sánh, nhưng Bubble Sort có thể đổi chỗ tới O(n²) lần, còn Selection Sort tối đa n-1 lần. Đổi lại Bubble Sort biết dừng sớm, Selection Sort thì không. Đây chính là chủ đề bài sau.

Lời kết

Bubble Sort là bài học tốt về cách đo một thuật toán: chỉ cần đếm số phép so sánh là thấy ngay vì sao O(n²) không đi xa được. Phần còn lại của series sẽ lần lượt đi tới những cách nhanh hơn rất nhiều.

Đây là bài 01/19 của series "Thuật toán & Cấu trúc dữ liệu - Giải thuật". Bản video ngắn có hoạt hình minh họa từng lượt "nổi bong bóng" nằm trên page Trà Đá Tech: https://www.facebook.com/profile.php?id=61596642752252

Bạn học Bubble Sort lần đầu khi nào, và đã bao giờ gặp nó trong code thật chưa? Hãy chia sẻ trong phần bình luận.

Nếu thấy bài viết hữu ích, hãy upvote và follow để theo dõi các bài tiếp theo.

Bài tiếp theo: Selection Sort - ít đổi chỗ nhất nhưng không bao giờ biết dừng sớm


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí