Thuật toán sắp xếp nổi bọt trong Python
Sau mỗi lượt, các giá trị lớn dần di chuyển về cuối danh sách.
Thuật toán sắp xếp nổi bọt trong Python là gì?
Sau mỗi lượt, các giá trị lớn dần di chuyển về cuối danh sách.
Sắp xếp bằng cách đổi chỗ liên tiếp hai phần tử kề nhau.
Khi nào nên sử dụng?
- Rèn luyện tư duy giải quyết vấn đề và cấu trúc dữ liệu.
- Xử lý dữ liệu khi cần kiểm soát rõ từng bước của thuật toán.
- Chuẩn bị cho bài tập, kỳ thi và phỏng vấn lập trình.
Mô phỏng Thuật toán sắp xếp nổi bọt 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ụ
main.py
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ả dự kiến
[1, 2, 4, 5, 8]Cách hoạt động
Hai phần tử sai thứ tự được đổi chỗ. O(n²) khiến thuật toán chủ yếu phù hợp để học.
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 sửa code theo các bài tập dưới đây để hiểu rõ cách hoạt động thay vì chỉ sao chép kết quả.
- Kiểm tra trường hợp rỗng, một phần tử và giá trị trùng lặp.
- In trạng thái sau từng bước để quan sát thuật toán.
- Đo thời gian với 100, 1.000 và 10.000 phần tử rồi so sánh cách giải khác.