Tổng quan
Bubble Sort là thuật toán sắp xếp nhập môn kinh điển. Nó liên tục duyệt qua danh sách, so sánh từng cặp phần tử liền kề và hoán đổi nếu chúng sai thứ tự, khiến các giá trị lớn nhất dần 'nổi' về cuối.
Vì chỉ so sánh các phần tử kề nhau, Bubble Sort rất dễ hình dung và cài đặt, nên thường được dạy đầu tiên — dù nó quá chậm với dữ liệu lớn.
Bubble Sort hoạt động thế nào?
- So sánh hai phần tử liền kề đầu tiên; hoán đổi nếu phần tử bên trái lớn hơn.
- Dịch sang phải một vị trí và lặp lại đến hết mảng — sau lượt này phần tử lớn nhất nằm cuối.
- Lặp lại các lượt trên phần đầu chưa sắp xếp, phần này ngắn dần một phần tử mỗi lượt.
- Dừng sớm nếu một lượt không có hoán đổi nào — mảng đã được sắp xếp.
Khi nào nên dùng?
- Dạy ý tưởng sắp xếp bằng so-sánh-và-hoán-đổi cho người mới.
- Mảng rất nhỏ hoặc gần như đã sắp, khi cơ chế dừng sớm khiến nó gần như tuyến tính.
- Tránh dùng với dữ liệu lớn — thời gian bậc hai khiến nó không thực tế.
Phân tích độ phức tạp
Mỗi trong n lượt có thể quét tới n phần tử, dẫn tới O(n²) phép so sánh ở trường hợp trung bình và xấu nhất. Trường hợp tốt nhất O(n) xảy ra với đầu vào đã sắp nhờ cơ chế dừng sớm khi không hoán đổi. Nó sắp xếp tại chỗ (O(1) bộ nhớ phụ) và ổn định.
Câu hỏi thường gặp
Bubble Sort có ổn định không?
Có. Nó chỉ hoán đổi các phần tử kề nhau sai thứ tự thực sự, nên các phần tử bằng nhau giữ nguyên thứ tự tương đối ban đầu.
Vì sao Bubble Sort bị coi là kém hiệu quả?
Nó thực hiện O(n²) phép so sánh và nhiều hoán đổi thừa, nên các thuật toán O(n log n) nhanh hơn như Merge Sort hay Quick Sort được ưu tiên cho công việc thực tế.