Sắp xếp chèn¶

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 chèn.

Thuật toán sắp xếp chèn¶

Ý tưởng¶

Hãy tưởng tượng hình ảnh cả lớp đang xếp một hàng dọc.

Xét một bạn Tèo nào đó. Lần lượt các bạn đứng trước Tèo mà cao hơn Tèo thì lùi về sau một vị trí, cho đến khi gặp một bạn không cao hơn Tèo thì dừng. Lúc này, do các bạn cao đã lùi về sau, một chỗ trống sẽ lộ ra cho Tèo đứng chèn vào.

Dựa vào cách thức trên, ý tưởng chính của thuật toán sắp xếp chèn là lặp lại nhiều lần thao tác di chuyển một phần tử lên trước các phần tử lớn hơn nó. Cụ thể như sau:

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
20
21
22
23
24
25
26
27
28
29

# Hàm sắp xếp chèn
def insertionSort(A):
    n = len(A)

    # Duyệt mảng A từ vị trí 1 đến cuối
    for i in range(1, n):        
        # Lưu giá trị A[i] vào biến tạm t
        t = A[i]       

        # Duyệt mảng con từ vị trí i - 1 ngược về đầu mảng
        j = i - 1
        while j >= 0 and A[j] > t:

            # Dịch chuyển A[j] về phía sau một vị trí
            A[j + 1] = A[j]

            # Giảm j để tiếp tục xét những A[j] mà lớn hơn t
            j = j - 1

        # Chèn t vào vị trí j + 1
        A[j + 1] = t  # (1)


# 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}')
    insertionSort(array)
    print(f'Mảng có thứ tự tăng dần: {array}')

1. Sau khi vòng lặp while kết thúc, j là vị trí mà A[j] nhỏ hơn hoặc bằng A[i], còn j + 1 là vị trí sẽ được A[i] đứng chèn vào.

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¶