Sắp xếp nổi bọt (bubble sort) trong Python
Xem giá trị lớn nhất nổi dần về cuối sau mỗi lượt, và dừng sớm khi list đã được sắp xếp.
- So sánh và hoán đổi hai phần tử kề nhau
- Vì sao mỗi lượt cố định thêm một giá trị
- Cờ swapped để dừng sớm
Từng lượt một
Vấn đề
Việc sắp xếp có mặt ở khắp nơi, và hiểu cách sắp xếp hoạt động giúp bạn đánh giá được code chạy nhanh hay chậm. Sắp xếp nổi bọt (bubble sort) là thuật toán sắp xếp dễ theo dõi từng bước nhất, nên thường được chọn làm ví dụ đầu tiên, dù chương trình thật dùng các thuật toán nhanh hơn.
Hình dung đời thường
Bubble sort giống xếp hàng học sinh theo chiều cao mà chỉ được đổi chỗ hai bạn đứng cạnh nhau. Đi dọc hàng và đổi chỗ mọi cặp mà bạn cao hơn đứng trước. Sau một lượt, bạn cao nhất đã ra tới cuối hàng, như bong bóng nổi lên mặt nước. Lặp lại cho tới khi một lượt không cần đổi chỗ nào.
result[index] > result[index + 1]👫 Bạn cao hơn có đang đứng trước không?result[index], result[index + 1] = ...🔄 Đổi chỗ hai bạn đứng cạnh nhaufor end in range(len(result) - 1, 0, -1):🚶 Đi lại dọc hàng, mỗi lượt ngắn đi một bạnif not swapped: break✅ Cả lượt không đổi chỗ nào: hàng đã xếp xongBubble sort đi qua list nhiều lượt, đổi chỗ các cặp phần tử cạnh nhau sai thứ tự, cho tới khi một lượt không đổi chỗ nào; nhìn chung thuật toán mất thời gian O(n²).
Những điểm quan trọng
result = values.copy()sắp xếp một bản sao, nên list của nơi gọi hàm không bị đổi.if result[index] > result[index + 1]:đổi chỗ một cặp sai thứ tự.endgiảm dần sau mỗi lượt, vì các giá trị lớn nhất đã nằm ở cuối.if not swapped: breakdừng sớm khi một lượt không đổi chỗ nào, nên dữ liệu đã có thứ tự chỉ cần một lượt.
Khi nào nên sử dụng?
- Học cách các thuật toán sắp xếp dựa trên so sánh hoạt động.
- List rất nhỏ trong công cụ dạy học và minh họa trực quan.
- Kiểm tra một list đã có thứ tự hay chưa chỉ trong một lượt.
Khi nào chưa cần
- Mọi chương trình thật:
sorted()vàlist.sort()nhanh hơn rất nhiều (O(n log n)) và đã được kiểm chứng. - List hơn vài trăm phần tử: số lần so sánh tăng theo bình phương độ dài.
Mô phỏng Sắp xếp nổi bọt (bubble sort) trong Python
O(n²)Nhấn Phát hoặc Từng bước để theo dõi từng phép so sánh và thay đổi dữ liệu.
Code ví dụ
def bubble_sort(values):
result = values.copy()
for end in range(len(result) - 1, 0, -1):
swapped = False
for index in range(end):
if result[index] > result[index + 1]:
result[index], result[index + 1] = result[index + 1], result[index]
swapped = True
if not swapped:
break
return result
print(bubble_sort([5, 1, 4, 2, 8]))
Kết quả khi chạy
[1, 2, 4, 5, 8]
Giải thích code
Sau mỗi lượt, giá trị lớn nhất trong phần chưa sắp xếp đã nằm đúng vị trí cuối cùng, nên lượt sau duyệt ngắn đi một phần tử. Biến swapped ghi nhận lượt đó có đổi chỗ hay không. Nếu không có lần đổi chỗ nào, danh sách đã được sắp xếp và vòng lặp dừng sớm. Trong trường hợp xấu nhất, độ phức tạp là O(n²), nên thuật toán này không phù hợp với dữ liệu lớn.
Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.
Bài tập mở rộng
Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.
- Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
- In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
- Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Lỗi hay gặp
Đi quá một vị trí
result[index + 1] vượt ra ngoài list khi index tới vị trí cuối.
for index in range(len(result)):
if result[index] > result[index + 1]:
for index in range(end):
if result[index] > result[index + 1]:
Bạn học xong bài này chưa?
Đánh dấu đã học để theo dõi tiến độ của bạn.
Luyện tập với thử thách
Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.
- Count Inversions Count the out-of-order pairs in a list. Khó
- Trung vị của một danh sách Tìm giá trị ở giữa của một danh sách sau khi sắp xếp. Dễ