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

Sắp xếp nổi bọt sắp xếp một mảng bằng cách so sánh và hoán đổi liên tục các phần tử liền kề. Quá trình này giống như các bong bóng khí nổi lên từ đáy đến đỉnh, do đó có tên gọi là sắp xếp nổi bọt.

Như minh họa trong hình dưới đây, quy trình nổi bọt có thể được mô phỏng bằng các thao tác hoán đổi phần tử: bắt đầu từ đầu ngoài cùng bên trái của mảng và duyệt sang bên phải, so sánh từng cặp phần tử liền kề, nếu "phần tử bên trái > phần tử bên phải" thì hoán đổi chúng. Sau khi hoàn thành lượt duyệt, phần tử lớn nhất sẽ được di chuyển về đầu ngoài cùng bên phải của mảng.

<1><2><3><4><5><6><7>

Quy trình thuật toán

Giả sử mảng có độ dài \(n\). Các bước của thuật toán sắp xếp nổi bọt được hiển thị trong hình dưới đây.

1. Đầu tiên, thực hiện thao tác "nổi bọt" trên \(n\) phần tử, hoán đổi phần tử lớn nhất của mảng về đúng vị trí của nó.
2. Tiếp theo, thực hiện thao tác "nổi bọt" trên \(n - 1\) phần tử còn lại, hoán đổi phần tử lớn thứ hai về đúng vị trí của nó.
3. Và cứ tiếp tục như vậy. Sau \(n - 1\) vòng "nổi bọt", tất cả \(n - 1\) phần tử lớn nhất đã được hoán đổi về đúng vị trí của chúng.
4. Phần tử duy nhất còn lại chắc chắn là phần tử nhỏ nhất, không cần sắp xếp, do đó quá trình sắp xếp mảng hoàn tất.

Mã nguồn ví dụ được hiển thị dưới đây:

[file]{bubble_sort}-[class]{}-[func]{bubble_sort}

Tối ưu hóa hiệu suất

Chúng ta có thể nhận thấy rằng nếu không có thao tác hoán đổi nào xảy ra trong một vòng "nổi bọt", điều đó có nghĩa là mảng đã được sắp xếp và thuật toán có thể kết thúc ngay lập tức. Do đó, chúng ta có thể thêm một biến cờ hiệu flag để phát hiện tình huống này và dừng thuật toán ngay khi nó xảy ra.

Sau tối ưu hóa này, độ phức tạp thời gian trong trường hợp xấu nhất và trung bình của thuật toán sắp xếp nổi bọt vẫn là \(O(n^2)\); tuy nhiên, khi mảng đầu vào đã được sắp xếp sẵn, độ phức tạp thời gian trong trường hợp tốt nhất sẽ trở thành \(O(n)\).

[file]{bubble_sort}-[class]{}-[func]{bubble_sort_with_flag}

Đặc điểm của thuật toán

• Độ phức tạp thời gian là \(O(n^2)\); mang tính thích ứng: Trong các vòng "nổi bọt" liên tiếp, phần mảng được duyệt qua có độ dài lần lượt là \(n - 1\), \(n - 2\), \(\dots\), \(2\), \(1\), tổng cộng là \((n - 1) n / 2\). Sau khi áp dụng tối ưu hóa với biến flag, độ phức tạp thời gian trong trường hợp tốt nhất có thể đạt \(O(n)\).
• Độ phức tạp không gian là \(O(1)\), sắp xếp tại chỗ: Các con trỏ \(i\) và \(j\) sử dụng một lượng không gian bổ sung không đổi.
• Sắp xếp ổn định: Các phần tử bằng nhau không bị hoán đổi trong quá trình "nổi bọt".