Sắp xếp nổi bọt¶

Bài toán và thuật toán sắp xếp¶

Tương tự bài học trước, ta chỉ xét bài toán đơn giản là sắp xếp mảng một chiều các số nguyên theo thứ tự tăng dần.

Về thuật toán, bài học này đề cập thuật toán sắp xếp nổi bọt.

Thuật toán sắp xếp nổi bọt¶

Ý tưởng¶

Hãy tưởng tượng hình ảnh các bọt nước ở dưới đáy nổi dần lên trên bề mặt. Khi ở dưới đáy, bọt nước có kích thước nhỏ và khi đến gần bề mặt, bọt nước có kích thước lớn dần.

Tạm xem đầu mảng là đáy nước và cuối mảng là bề mặt, ta sắp xếp mảng bằng cách lần lượt cho các phần tử lớn hơn nổi lên bề mặt. Cụ thể như sau:

Như vậy, sau mỗi lần lặp của vòng lặp trong (biến j), các phần tử lớn sẽ trôi về phía cuối mảng, và sau mỗi lần lặp của vòng lặp ngoài (biến i), phần tử lớn nhất sẽ về đúng vị trí của nó là ở cuối mảng.

Có thể thấy, với mỗi lần lặp tiếp theo của vòng lặp ngoài (biến i), phạm vi duyệt sẽ thu nhỏ lại, từ đầu mảng cho đến trước phần tử lớn nhất của lần duyệt trước đó.

Ví dụ¶

Lưu đồ thuật toán¶

Trực quan hóa thuật toán¶

Chương trình minh họa¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

# Hàm sắp xếp nổi bọt
def bubbleSort(A):
    n = len(A)

    # Duyệt mảng A từ vị trí 0 đến áp cuối
    for i in range(n - 1):
        # Duyệt mảng con từ vị trí 0 đến trước i phần tử cuối
        for j in range(n - 1 - i):
            # So sánh và hoán vị hai phần tử cạnh nhau
            if A[j] > A[j + 1]:
                A[j], A[j + 1] = A[j + 1], A[j]


# Chương trình chính
if __name__ == '__main__':
    array = [1, 7, 4, 0, 9, 4, 8, 8]
    print(f'Mảng gốc chưa có thứ tự: {array}')
    bubbleSort(array)
    print(f'Mảng có thứ tự tăng dần: {array}')

Output:

Mảng gốc chưa có thứ tự: [1, 7, 4, 0, 9, 4, 8, 8]
Mảng có thứ tự tăng dần: [0, 1, 4, 4, 7, 8, 8, 9]

Sơ đồ tóm tắt nội dung¶

Google Colab¶

Các đoạn mã trong bài này được đặt tại Google Colab để bạn có thể thử nghiệm theo cách của riêng mình.

Some English words¶