Sắp xếp nổi bọt (Bubble Sort) là một trong những thuật toán phổ biến trong mảng kiến thức về Cấu trúc dữ liệu và giải thuật. Nó có thể được thực hiện bởi hầu hết các ngôn ngữ lập trình như C/C++, Python, Java, PHP… và thường được viết dưới dạng hai vòng lặp for lồng nhau. Dưới đây là một ví dụ về cách thức thực thi thuật toán này trong Python.
def bubbleSort(array):
n = len(array)
for i in range(n-1):
for j in range(n-1 - i):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
return arrayKết quả trả về của hàm này là một list (array). Tôi có làm một video giải thích về cách thức hoạt động của hàm này, các bạn có thể tham khảo tại đây:
Tôi đã chạy thử hàm này với một list gồm 35 số nguyên được sắp xếp ngẫu nhiên, đồng thời có điều chỉnh đôi chút trong code để mỗi vòng lặp đều xuất ra màn hình kết quả sắp xếp của vòng lặp đó. Kết quả thu được là một list đã được sắp xếp theo thứ tự từ nhỏ đến lớn, như hình dưới đây:
Trong hình này, dòng đầu là list ban đầu, vẫn chưa được sắp xếp, mỗi dòng tiếp theo là một vòng lặp, kết quả của mỗi vòng lặp này là phần tử lớn nhất được di chuyển về vị trí cuối của list. Cuối mỗi dòng là tổng số bước đã thực hiện của thuật toán, số bước của mỗi vòng sẽ giảm dần từ n-1 đến 1. Vậy tổng số bước của thuật toán là $\dfrac{n(n-1)}{2}$ (tổng $n-1$ số hạng đầu của cấp số cộng).
Vấn đề đáng nói ở đây là list này đã được sắp xếp xong từ vòng lặp thứ 26, với tối đa 559 bước, nhưng chương trình vẫn chưa nhận ra và vẫn tiếp tục quét tiếp 8 vòng nữa, nâng tổng số bước lên 595. Rất rõ ràng, thuật toán này chưa tốt.
Sau quá trình tìm tòi trên các diễn đàn, tôi đã tìm ra thuật toán khá hơn. Thay vì sử dụng 2 vòng lặp for lồng nhau, ta sẽ dùng một vòng lặp while kết hợp với vòng lặp for. Điều khác biệt ở đây là, vòng lặp while có thể kiểm tra điều kiện trước khi thực hiện khối lệnh bên trong. Dưới đây là hàm Python mà tôi đã chạy được:
def bubblesort_using_whileloop(list):
n = len(list)
sortFinished = False
while sortFinished is False:
sortFinished = True
for i in range(n-1):
if list[i] > list[i+1]:
list[i], list[i+1] = list[i+1], list[i]
sortFinished = False
n -= 1
return listTrước hết, có một biến đặc biệt để nhận biết rằng list đã được sắp xếp theo thứ tự hết chưa, mặc định là False. Khởi đầu lệnh while, biến sortFinished sẽ nhận giá trị True, nhưng nếu quét một vòng lặp for mà phát hiện có cặp số chưa đúng thứ tự thì biến sortFinished sẽ trở thành False, và khi đó, vòng lặp while sẽ lại chạy tiếp. Với ý tưởng này, thuật toán sẽ dừng lại sớm hơn, có điều, dù list đã được sắp xếp hết thì vẫn cần một vòng lặp for cuối để kiểm tra. Dưới đây là kết quả chạy thuật toán:
Lần này, số vòng lặp chỉ còn 21, trong đó vòng lặp cuối chỉ để đảm bảo rằng list đã được sắp xếp toàn bộ. Dễ thấy, tổng số bước đã giảm đáng kể. Qua vài lần chạy thử với các list ngẫu nhiên, tôi nhận thấy
- Tổng số bước của thuật toán thứ nhất (for + for) là cố định
- Tổng số bước của thuật toán thứ hai (while + for) biến động tùy theo list, có trường hợp tổng số bước là ngang bằng với thuật toán thứ nhất.
Nhin chung, cả hai thuật toán này đều là sắp xếp nổi bọt, độ phức tạp vẫn là $n^2$, nhưng ít ra thì thuật toán thứ hai vẫn dễ chấp nhận hơn so với thuật toán thứ nhất. Tôi sẽ áp dụng cách này cho các ngôn ngữ lập trình khác.