Sắp xếp nổi bọt (Bubble Sort) – Minh họa trong Python và Scratch

Sắp xếp nổi bọt (Bubble Sort) – Minh họa trong Python và Scratch

Sắp xếp nổi bọt (Bubble Sort) là gì?

Minh họa sắp xếp nổi bọt (Bubble Sort) bằng Python:

def bubble_sort(arr):
    n = len(arr)
    
    for i in range(n):
        # Duyệt qua từng cặp phần tử liên tiếp
        # và hoán đổi chúng nếu chúng không theo thứ tự
        for j in range(n - i - 1):
            if arr[j]  > arr[j + 1] 
:
                arr[j] , arr[j + 1]  = arr[j + 1] , arr[j] 





    
    return arr

# Ví dụ sử dụng
arr = [64, 34, 25, 12, 22, 11, 90] 


sorted_arr = bubble_sort(arr)
print("Danh sách đã sắp xếp:", sorted_arr)

Kết quả:Danh sách đã sắp xếp: [11, 12, 22, 25, 34, 64, 90]

Trong ví dụ trên, chúng ta triển khai hàm bubble_sort để sắp xếp một danh sách (arr). Trong vòng lặp bên ngoài, chúng ta duyệt qua từng phần tử và trong vòng lặp bên trong, chúng ta so sánh các cặp phần tử liên tiếp và hoán đổi chúng nếu chúng không theo thứ tự. Quá trình này được lặp lại cho đến khi danh sách được sắp xếp hoàn toàn. Kết quả cuối cùng là danh sách đã sắp xếp.

Thuật toán sắp xếp nổi bọt (Bubble Sort) trong Scratch:

Dưới đây là một ví dụ về cách triển khai thuật toán sắp xếp nổi bọt (Bubble Sort) bằng Scratch, một môi trường lập trình trực quan dành cho trẻ em:

1. Tạo một danh sách các số cần sắp xếp. Trong ví dụ này, chúng ta sử dụng một danh sách gồm các số nguyên từ 0 đến 9 thứ tự lung tung
2. Tạo một biến length và đặt giá trị bằng độ dài của danh sách.
3. Tạo một biến swapped và đặt giá trị ban đầu là True để bắt đầu vòng lặp.
4. Tạo một vòng lặp chạy cho đến khi swapped là False. Trong mỗi vòng lặp, ta sẽ thiết lập swapped thành False và thực hiện sắp xếp.
5. Trong vòng lặp, duyệt qua từng cặp phần tử liên tiếp trong danh sách.
   • So sánh hai phần tử và nếu phần tử sau lớn hơn phần tử trước, thực hiện hoán đổi vị trí của chúng và đặt swapped thành True.
6. Đặt swapped thành True nếu có bất kỳ hoán đổi nào xảy ra trong vòng lặp.
7. Khi vòng lặp kết thúc và không có hoán đổi nào xảy ra, ta có thể kết luận rằng danh sách đã được sắp xếp.
8. In danh sách đã sắp xếp.

Trong ví dụ trên, danh sách sẽ được hiển thị trước và sau khi sắp xếp. Mỗi số được đại diện bằng một hình tròn và các số đã sắp xếp sẽ được di chuyển lên trên. Khi không có hoán đổi nào xảy ra nữa, thuật toán dừng lại và kết quả cuối cùng được hiển thị.

Lưu ý rằng việc triển khai thuật toán sắp xếp nổi bọt trong Scratch có thể đòi hỏi sự tương tác với các khối lệnh, và hình ảnh minh họa chỉ mang tính chất đại diện cho cách thuật toán hoạt động chứ không phải là một chương trình Scratch hoàn chỉnh.