Insertion Sort (Sắp xếp chèn) trong Python là gì?

Insertion sort là phương pháp sắp xếp mảng đơn giản. Mảng được chia ảo thành phần đã sắp xếp và chưa sắp xếp. Lấy phần tử từ phần chưa sắp xếp, chèn vào vị trí đúng trong phần đã sắp xếp.

• Duyệt mảng từ 1 đến n.
• Nếu phần tử tại i lớn hơn tiền nhiệm, giữ nguyên.
• Nếu nhỏ hơn, dịch trái cho đến khi tìm thấy tiền nhiệm nhỏ hơn hoặc về đầu mảng.

Ví dụ minh họa

Mảng: [4, 6, 1, 7, 2, 5]

Duyệt từ index 1:

Index 1: 6 > 4 → không đổi.

Index 2: 1 < 6 → dịch trái về index 0 → [1, 4, 6, 7, 2, 5]

Index 3: 7 > 6 → không đổi.

Index 4: 2 < 7 → dịch trái qua 6, 4, dừng trước 1 → [1, 2, 4, 6, 7, 5]

Index 5: 5 < 7 → dịch trái qua 7, 6, dừng trước 4 → [1, 2, 4, 5, 6, 7]

Insertion sort là thuật toán in-place, độ phức tạp thời gian O(n²), không gian O(1).

Ví dụ code

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

arr = [4, 6, 1, 7, 2, 5]
insertionSort(arr)
for i in range(len(arr)):
    print(arr[i], end=" ")

Kết quả

1 2 4 5 6 7