Bỏ qua

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

Tóm lược nội dung

Bài này trình bày thuật toán sắp xếp nổi bọt.

Khái quát

Xem lại khái quát về bài toán và thuật toán sắp xếp tại đây.

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.

Nếu 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:

Cho i chạy từ đầu đến áp cuối, lặp thao tác:

  • Duyệt từng phần tử A[j] từ 0 đến vị trí trước i phần tử cuối, tức vị trí trước n – 1 – i, thực hiện:

    So sánh và hoán vị hai phần tử cạnh nhau A[j] và A[j + 1] sao cho phần tử nhỏ hơn đứng trước và phần tử lớn hơn đứng 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ó ở 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 đó.

Thuật toán có thể được phác hoạ như hình sau:

Phác hoạ ý tưởng chính

Ví dụ minh hoạ

Ví dụ minh hoạ tiến trình sắp xếp nổi bọt

Lưu đồ

Lưu đồ sắp xếp nổi bọt

Trực quan hoá

Viết chương trình

1. Nạp thư viện numpy.

1
import numpy as np

2. Viết hàm bubble_sort() để thực hiện thuật toán sắp xếp nổi bọt.

 4
 5
 6
 7
 8
 9
10
11
12
13
14
def bubble_sort(A):
    # Lấy số lượng phần tử của mảng A
    n = len(A)

    # Cho i chạy từ 0 đến n - 2
    for i in range(n - 1):
        # Duyệt từng phần tử A[j] từ 0 đến trước n - 1 - 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]

3. Viết chương trình chính.

Trong chương trình chính, ta tạm thời bỏ qua việc cho người dùng nhập mảng. Thay vào đó, ta khởi tạo mảng cố định, rồi gọi hàm bubble_sort() để sắp xếp mảng Array.

18
19
20
21
22
23
24
25
26
27
28
29
if __name__ == '__main__':
    # Khởi tạo mảng Array
    Array = np.array([1, 7, 4, 0, 9, 4, 8, 8])

    # In mảng ban đầu
    print(f'Mảng ban đầu chưa sắp xếp: {Array}')

    # Gọi hàm bubble_sort()
    bubble_sort(Array)

    # In mảng mới
    print(f'Mảng mới sau khi sắp xếp: {Array}')

4. Chạy chương trình trên, kết quả như sau:

Mảng ban đầu chưa sắp xếp: [1 7 4 0 9 4 8 8]
Mảng mới sau khi sắp xếp: [0 1 4 4 7 8 8 9]

Mã nguồn

Code đầy đủ được đặt tại:

Sơ đồ tóm tắt

Some English words

Vietnamese Tiếng Anh
hoán vị (hai phần tử) swap
sắp xếp nổi bọt bubble sort
so sánh compare
Bao tôi ly cafe 🧋 nhé!