Sắp xếp nổi bọt

Sắp xếp nổi bọt là thuật toán sắp xếp dễ mô tả nhất: so sánh hai phần tử kề nhau, hoán đổi nếu sai thứ tự, rồi lặp lại. Nó chậm với danh sách dài, nhưng từng bước đều dễ theo dõi, nên là thuật toán kinh điển đầu tiên để quan sát.

Các cột cao thấp khác nhau đang được sắp xếp, hai cột kề nhau được làm nổi bật để hoán đổi và các cột cao nhất đã đúng chỗ ở cuối
Các cột cao thấp khác nhau đang được sắp xếp, hai cột kề nhau được làm nổi bật để hoán đổi và các cột cao nhất đã đúng chỗ ở cuối

Ý tưởng

Duyệt danh sách từ trái sang phải và xét từng cặp kề nhau. Nếu giá trị bên trái lớn hơn bên phải, hoán đổi chúng. Khi tới cuối, giá trị lớn nhất đã được đưa đến tận vị trí cuối cùng, như bọt khí nổi lên mặt nước. Mỗi lần duyệt như vậy gọi là một lượt. Lặp lại các lượt cho đến khi danh sách được sắp xếp.

Ví dụ

Lấy 5, 1, 4, 2, 8. Lượt đầu so sánh 5 và 1 rồi hoán đổi, sau đó 5 và 4 (hoán đổi), 5 và 2 (hoán đổi), và 5 và 8 (không đổi): 1, 4, 2, 5, 8. Số 8 giờ đã ở vị trí cuối cùng. Lượt thứ hai so sánh 1 và 4 (không đổi), 4 và 2 (hoán đổi) và 4 và 5 (không đổi): 1, 2, 4, 5, 8. Lượt thứ ba không có hoán đổi nào, nên danh sách đã được sắp xếp: 9 phép so sánh và 4 lần hoán đổi.

Vì sao mỗi lượt đưa thêm một giá trị về đúng chỗ

Trong một lượt, giá trị lớn nhất gặp được cho đến lúc đó luôn được mang theo: khi lượt duyệt chạm tới nó, mỗi phép so sánh lại đẩy nó sang phải thêm một vị trí. Vì vậy lượt đầu đặt giá trị lớn nhất ở cuối, lượt hai đặt giá trị lớn thứ hai ngay trước nó, và cứ thế. Sau lượt k, k vị trí cuối đã cố định, và lượt tiếp theo có thể dừng sớm hơn một vị trí. Đó là lý do các lượt ngắn dần.

Số hoán đổi bằng số nghịch thế

Nghịch thế là một cặp giá trị nằm sai thứ tự: một giá trị lớn hơn đứng ở đâu đó trước một giá trị nhỏ hơn. Hoán đổi hai phần tử kề nhau đang sai thứ tự xóa đúng một nghịch thế và không tạo ra nghịch thế mới. Vì vậy sắp xếp nổi bọt thực hiện đúng số lần hoán đổi bằng số nghịch thế của danh sách ban đầu, bất kể thứ tự các phép so sánh. Danh sách đã sắp xếp không có nghịch thế nào; danh sách đảo ngược gồm n giá trị có n(n − 1)/2, nhiều nhất có thể.

Dừng sớm và chi phí

Nếu cả một lượt không có hoán đổi nào, mọi cặp kề nhau đều đúng thứ tự và danh sách đã được sắp xếp. Nhờ kiểm tra điều đó, sắp xếp nổi bọt hoàn thành danh sách đã sắp xếp chỉ trong một lượt gồm n − 1 phép so sánh. Trong trường hợp xấu nhất, nó vẫn cần n − 1 lượt và n(n − 1)/2 phép so sánh, và trung bình số lần hoán đổi là n(n − 1)/4. Cả hai đều tăng theo n², nên khi danh sách dài gấp đôi, thời gian sắp xếp tăng khoảng bốn lần.

Sắp xếp nổi bọt là thuật toán ổn định: các giá trị bằng nhau không bao giờ bị hoán đổi, nên giữ nguyên thứ tự. Nó sắp xếp tại chỗ, không cần thêm bộ nhớ. Sắp xếp chèn có cùng các tính chất đó và thường cần ít bước hơn, còn sắp xếp trộn và sắp xếp nhanh tốn thời gian tỉ lệ với n log n, ít hơn nhiều trên danh sách dài.

Tự khám phá

Mở ứng dụng và nhấn Phát, hoặc nhấn Bước để đi từng phép so sánh. Hai giá trị đang được so sánh được làm nổi bật, lần hoán đổi có màu riêng, và các giá trị đã đúng chỗ chuyển sang màu xanh lá. Thử danh sách đảo ngược để xem trường hợp xấu nhất, danh sách gần như đã sắp xếp để thấy dừng sớm kết thúc sau vài lượt, hoặc nhập các số trong ví dụ ở trên.

Câu hỏi thường gặp

Độ phức tạp thời gian của sắp xếp nổi bọt là bao nhiêu?

O(n²) trong trường hợp xấu nhất và trung bình: tối đa n(n − 1)/2 phép so sánh với n giá trị. Với dừng sớm, danh sách đã sắp xếp sẵn chỉ tốn O(n), tức một lượt. Nó chỉ cần O(1) bộ nhớ phụ.

Sắp xếp nổi bọt có ổn định không?

Có. Nó chỉ hoán đổi hai phần tử kề nhau khi số bên trái lớn hơn hẳn, nên các giá trị bằng nhau không bao giờ vượt qua nhau và giữ nguyên thứ tự ban đầu.

Sắp xếp nổi bọt khác sắp xếp chèn thế nào?

Cả hai đều hoán đổi các phần tử kề nhau và đều thực hiện số lần hoán đổi bằng số nghịch thế. Sắp xếp nổi bọt duyệt hết phần chưa sắp xếp ở mỗi lượt; sắp xếp chèn chỉ lùi mỗi giá trị mới về đến chỗ cần thiết, nên thường ít phép so sánh hơn, nhất là với danh sách gần như đã sắp xếp.

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

Chủ yếu để giảng dạy, và cho danh sách rất ngắn khi sự đơn giản quan trọng hơn tốc độ. Với dữ liệu lớn hơn, hàm sắp xếp có sẵn trong ngôn ngữ lập trình của bạn nhanh hơn nhiều.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Thử sắp xếp nổi bọt