Sắp xếp nổi bọt (bubble sort) trong Python
Bài 14/20 · Chương 23
Cấu trúc dữ liệu và giải thuật
- 9 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 12
Sắp xếp nổi bọt (bubble sort) là thuật toán sắp xếp đi qua list nhiều lượt, mỗi lần so hai phần tử đứng cạnh nhau và đổi chỗ chúng khi phần tử trước lớn hơn. Bạn tự viết nó khi muốn thấy rõ một thuật toán sắp xếp làm việc từng bước, ví dụ xếp số phút giao dịch của khách ở quầy từ ngắn tới dài.
Cần biết trước: vòng lặp lồng nhau, biến cờ và hoán đổi bằng unpacking.
Một lượt nổi bọt
Quầy giao dịch ghi số phút của năm khách: [7, 3, 9, 2, 5]. Một lượt nổi bọt đi từ đầu list, so từng cặp kề nhau phut[j] và phut[j + 1], đổi chỗ khi số trước lớn hơn số sau. Dòng print cho thấy list sau mỗi cặp:
phut = [7, 3, 9, 2, 5]
for j in range(len(phut) - 1):
if phut[j] > phut[j + 1]:
phut[j], phut[j + 1] = phut[j + 1], phut[j]
print(j, phut)KẾT QUẢ
0 [3, 7, 9, 2, 5]
1 [3, 7, 9, 2, 5]
2 [3, 7, 2, 9, 5]
3 [3, 7, 2, 5, 9]List có năm phần tử nên có bốn cặp kề nhau, và j chạy từ 0 tới 3. Cặp 7 và 9 đã đúng thứ tự nên đứng yên. Số 9 gặp toàn số nhỏ hơn phía sau nên bị đổi chỗ liên tiếp, trôi dần về cuối như bong bóng nổi lên mặt nước. Hết một lượt, phần tử lớn nhất chắc chắn nằm ở cuối, còn phần trước nó chưa chắc đã xếp xong.
Viết bubble sort bằng hai vòng lặp lồng nhau
Một lượt chỉ đưa được một phần tử về đúng chỗ, nên cần một vòng ngoài lặp lại lượt đó. Sau lượt thứ i + 1, i + 1 phần tử cuối đã đứng yên, vì vậy vòng trong đi ngắn dần bằng range(n - 1 - i):
def bubble_sort(ds):
ds = ds.copy()
n = len(ds)
for i in range(n - 1):
for j in range(n - 1 - i):
if ds[j] > ds[j + 1]:
ds[j], ds[j + 1] = ds[j + 1], ds[j]
print("Sau lượt", i + 1, ds)
return ds
phut = [7, 3, 9, 2, 5]
print(bubble_sort(phut), phut)KẾT QUẢ
Sau lượt 1 [3, 7, 2, 5, 9]
Sau lượt 2 [3, 2, 5, 7, 9]
Sau lượt 3 [2, 3, 5, 7, 9]
Sau lượt 4 [2, 3, 5, 7, 9]
[2, 3, 5, 7, 9] [7, 3, 9, 2, 5]Mỗi lượt có thêm một số về đúng chỗ ở cuối: 9, rồi 7, rồi 5. List n phần tử cần tối đa n - 1 lượt, vì khi n - 1 số lớn đã về cuối thì số còn lại ở đầu tự đúng chỗ. Dòng ds = ds.copy() làm việc trên một bản sao, nên phut của nơi gọi giữ nguyên (xem bài sao chép list). Bỏ dòng đó thì hàm sắp xếp tại chỗ, đúng như bubble sort trong sách giáo khoa, nhưng list gốc bị đổi.
Dừng sớm bằng biến cờ
Ở ví dụ trên, lượt 4 không đổi chỗ lần nào mà vẫn chạy. Một lượt không đổi chỗ nghĩa là mọi cặp kề nhau đã đúng thứ tự, tức list đã xếp xong. Biến cờ da_doi ghi lại lượt vừa chạy có đổi chỗ hay không, và break dừng vòng ngoài khi cờ vẫn là False:
def bubble_sort(ds):
ds = ds.copy()
so_luot = 0
for i in range(len(ds) - 1):
da_doi = False
for j in range(len(ds) - 1 - i):
if ds[j] > ds[j + 1]:
ds[j], ds[j + 1] = ds[j + 1], ds[j]
da_doi = True
so_luot += 1
if not da_doi:
break
return ds, so_luot
print(bubble_sort([2, 3, 5, 7, 4, 9]))
print(bubble_sort([9, 7, 5, 4, 3, 2]))KẾT QUẢ
([2, 3, 4, 5, 7, 9], 3)
([2, 3, 4, 5, 7, 9], 5)Dòng if not da_doi: break nằm ở thân vòng ngoài, sau vòng trong, nên break dừng hẳn vòng ngoài. Cờ phải được đặt lại thành False ở đầu mỗi lượt: đặt một lần trước vòng ngoài thì sau lần đổi chỗ đầu tiên nó mãi là True. List gần đúng thứ tự chỉ cần ba lượt, còn list xếp ngược vẫn cần đủ năm lượt. Đổi [2, 3, 5, 7, 4, 9] thành [2, 3, 4, 5, 7, 9] rồi chạy lại: dòng đầu in ([2, 3, 4, 5, 7, 9], 1).
Ổn định, tại chỗ và vì sao bubble sort chậm
Khi sắp xếp theo một phần của bản ghi, như số phút của từng khách, hai khách có thể cùng số phút. Bubble sort chỉ đổi chỗ khi số trước lớn hơn hẳn, nên hai khách bằng nhau không bao giờ vượt qua nhau. Thuật toán giữ thứ tự gặp trước của các phần tử bằng nhau như vậy là sắp xếp ổn định (bài thuật toán sắp xếp so tính chất này giữa các thuật toán):
def xep_theo_phut(hang_cho):
ds = hang_cho.copy()
for i in range(len(ds) - 1):
for j in range(len(ds) - 1 - i):
if ds[j][1] > ds[j + 1][1]:
ds[j], ds[j + 1] = ds[j + 1], ds[j]
return ds
hang_cho = [("Lan", 6), ("Minh", 3), ("Ngọc", 6), ("Quân", 3)]
print(xep_theo_phut(hang_cho))KẾT QUẢ
[('Minh', 3), ('Quân', 3), ('Lan', 6), ('Ngọc', 6)]Minh đến trước Quân và vẫn đứng trước Quân, Lan vẫn đứng trước Ngọc.
Bubble sort cũng là thuật toán tại chỗ: nó chỉ đổi chỗ phần tử bên trong list, không cần list phụ. Cái giá là số phép so sánh. Không dừng sớm, list n phần tử tốn (n - 1) + (n - 2) + … + 1 phép so sánh, tức n * (n - 1) // 2:
def dem_so_sanh(n):
ds = list(range(n, 0, -1))
dem = 0
for i in range(n - 1):
for j in range(n - 1 - i):
dem += 1
if ds[j] > ds[j + 1]:
ds[j], ds[j + 1] = ds[j + 1], ds[j]
return dem
for n in [10, 100, 1000]:
print(n, "phần tử:", dem_so_sanh(n), "phép so sánh")KẾT QUẢ
10 phần tử: 45 phép so sánh
100 phần tử: 4950 phép so sánh
1000 phần tử: 499500 phép so sánhDãy dài gấp mười thì số phép so sánh tăng khoảng một trăm lần: đó là độ phức tạp O(n²) của bài Big O. Với list đã xếp sẵn, bản có cờ chỉ chạy một lượt, tức O(n). Trong code thật, bạn dùng sort() hay sorted() của bài sắp xếp list.
Kiểm tra nhanh
Chạy một lượt nổi bọt như ví dụ đầu bài trên list
[8, 1, 6, 2]. Sau lượt đó list là gì?[1, 6, 2, 8][1, 2, 6, 8][1, 8, 6, 2]
Vòng trong của bubble sort viết
for j in range(n - i):, vớin = len(ds). Chạy hàm trên[7, 3, 9]thì sao?- List được xếp đúng, chỉ chậm hơn một chút
- Báo lỗi IndexError, vì
ds[j + 1]vượt chỉ số cuối - Vòng lặp chạy mãi không dừng
Những điều nào đúng với bubble sort có biến cờ dừng sớm như bài viết?
- List đã xếp sẵn
nphần tử chỉ tốn một lượt, tứcn - 1phép so sánh - List xếp ngược cũng dừng sau một lượt
- So bằng
>giữ nguyên thứ tự của hai khách cùng số phút - So bằng
>=làm thuật toán dừng sớm hơn
- List đã xếp sẵn
Không có cờ dừng sớm, bubble sort làm bao nhiêu phép so sánh để xếp một list 20 phần tử?
- 400
- 20
- 190
- 380
Bài tập
Ghi lại từng lượt nổi bọt
Quầy giao dịch muốn xem bubble sort xếp list số phút giao dịch tăng dần ra sao. Viết thân hàm luot_noi_bot(so_phut): mỗi lượt đi từ đầu tới hết phần chưa xếp, đổi chỗ hai phần tử kề nhau khi phần tử trước lớn hơn. Sau mỗi lượt có ít nhất một lần đổi chỗ, ghi một bản sao của list. Lượt đầu tiên không đổi chỗ thì dừng bằng break và không ghi lượt đó. Không dùng sorted() hay sort(), và không sửa so_phut.
Ví dụ: luot_noi_bot([7, 3, 9, 2, 5]) trả về [[3, 7, 2, 5, 9], [3, 2, 5, 7, 9], [2, 3, 5, 7, 9]].
Trả về: trạng thái của list sau từng lượt có đổi chỗ, một list gồm các list.
def luot_noi_bot(so_phut):
pass # Viết thân hàm thay cho dòng nàyTóm tắt
Mỗi lượt bubble sort so từng cặp kề nhau và đổi chỗ khi phần tử trước lớn hơn, nên phần tử lớn nhất trôi về cuối.
List
nphần tử cón - 1cặp kề nhau; lượt thứi + 1chỉ cầnrange(n - 1 - i).Biến cờ đặt lại
Falseở đầu mỗi lượt; lượt không đổi chỗ thìbreakdừng vòng ngoài.Không dừng sớm, bubble sort tốn
n * (n - 1) // 2phép so sánh: O(n²).So bằng
>giữ thứ tự gặp trước của phần tử bằng nhau (ổn định);>=làm mất tính chất đó.
Câu hỏi thường gặp
Có nên dùng sắp xếp nổi bọt trong code thật không?
Thường là không. sort() và sorted() của Python nhanh hơn hẳn với dãy dài và cũng ổn định. Bubble sort đáng học vì nó cho thấy rõ so sánh, đổi chỗ và biến cờ làm việc ra sao. Bài thuật toán sắp xếp so các thuật toán theo số bước và cho biết khi nào chọn cái nào.
Thuật toán sắp xếp nổi bọt có độ phức tạp bao nhiêu?
Trường hợp xấu, list xếp ngược, cần n * (n - 1) // 2 phép so sánh, tức O(n²). Trường hợp tốt, list đã xếp sẵn, bản có biến cờ chỉ chạy một lượt nên là O(n). Bộ nhớ thêm là O(1) vì thuật toán chỉ đổi chỗ trong list. Bài Big O giải thích O(n) và O(n²) nghĩa là gì.
Muốn xếp giảm dần bằng bubble sort trong Python thì sửa chỗ nào?
Chỉ cần đảo phép so: đổi chỗ khi phần tử trước nhỏ hơn hẳn, if ds[j] < ds[j + 1]:. Khi đó phần tử nhỏ nhất trôi về cuối sau mỗi lượt. Giữ phép so hẳn (<, không <=) để thuật toán vẫn ổn định.
Sắp xếp nổi bọt khác sắp xếp chọn ở đâu?
Bubble sort đổi chỗ nhiều lần trong một lượt, mỗi lần một cặp kề nhau. Sắp xếp chọn mỗi lượt chỉ tìm phần tử nhỏ nhất rồi đổi chỗ đúng một lần, nên ít đổi chỗ hơn nhưng không dừng sớm được. Sắp xếp chèn thì chèn từng phần tử vào phần đã xếp ở đầu list.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.