/codegym.vn/ - 153
Có thể tiến hành theo hướng từ trên xuống (bên trái sang) hoặc từ dưới lên (bên phải
sang). Sắp xếp nổi bọt còn có tên là sắp xếp bằng so sánh trực tiếp. Nó sử dụng phép
so sánh các phần tử nên là một giải thuật sắp xếp kiểu so sánh.
Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi mà độ phức tạp
trong trường hợp xấu nhất và trường hợp trung bình là Ο(n
2
) với n là số phần tử.
Giải thuật sắp xếp nổi bọt là giải thuật chậm nhất trong số các giải thuật sắp xếp cơ
bản. Giải thuật này còn chậm hơn giải thuật đổi chỗ trực tiếp mặc dù số lần so sánh
bằng nhau, nhưng do đổi chỗ hai phần tử kề nhau nên số lần đổi chỗ nhiều hơn.
Thuật toán này có tên gọi là “nổi bọt” vì hình tượng các giá trị nhỏ hơn (trong trường
hợp sắp xếp giảm dần) hoặc lớn hơn (trong trường hợp sắp xếp tăng dần) lần lượt
nổi lên phía trên của danh sách.
Giải thuật
Sắp xếp từ trên xuống
Giả sử dãy cần sắp xếp có n phần tử, trật tự sắp xếp là tăng dần. Khi tiến hành từ
trên xuống, ta so sánh hai phần tử đầu tiên, nếu phần tử đứng trước lớn hơn phần tử
đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử thứ hai
và thứ ba và tiếp tục cho đến cuối tập hợp dữ liệu, nghĩa là so sánh (và đổi chỗ nếu
cần) phần tử thứ n-1 với phần tử thứ n. Sau bước này phần tử cuối cùng chính là
phần tử lớn nhất của dãy.
Sau đó, quay lại so sánh (và đổi chỗ nếu cần) hai phần tử đầu cho đến khi gặp phần
tử thứ n-2....
Ghi chú: Nếu trong một lần duyệt, không phải đổi chỗ bất cứ cặp phần tử nào thì
danh sách đã được sắp xếp xong.
Ví dụ: Để sắp xếp 6 phần tử (2 9 5 4 8 1) theo trật tự tăng dần:
Chúng ta so sánh hai phần tử đầu tiên là 2 và 9, chúng đã đúng trật tự cho nên không
cần hoán đổi gì cả.
2
9
5
4
8
1
Tiếp theo chúng ta so sánh hai phần tử là 9 và 5, chúng đang không ở đúng trật tự (5
phải đứng trước 9) cho nên chúng ta phải hoán đổi vị trí của 2 phần tử này.
2
5
9
4
8
1
Tiếp theo chúng ta so sánh hai phần tử là 9 và 4, phải hoán đổi vị trí của chúng.
2
5
4
9
8
1
Tiếp theo chúng ta so sánh hai phần tử 9 và 8, phải hoán đổi vị trí của chúng.
2
5
4
8
9
1
Cuối cùng so sánh hai phần tử 9 và 1, phải hoán đổi vị trí của chúng.
