Thuật toán sắp xếp chèn (Insertion sort)

Thuật toán sắp xếp chèn (Insertion sort) là một trong số thuật toán sắp xếp đơn giản nhất trong các thuật toán sắp xếp cơ bản. Cách thức hoạt động của thuật toán này như sau:

1. Bắt đầu với danh sách chưa sắp xếp, ta lấy phần tử đầu tiên và chèn nó vào danh sách đã sắp xếp.
2. Tiếp tục lấy phần tử tiếp theo, so sánh với các phần tử trong danh sách đã sắp xếp để tìm vị trí thích hợp để chèn phần tử đã lấy.
3. Lặp lại quá trình trên cho đến khi danh sách được sắp xếp hoàn toàn.

Độ phức tạp của thuật toán sắp xếp chèn (Insertion sort) là O(n^2), tương đương với thuật toán sắp xếp nổi bọt (Bubble Sort) và thuật toán sắp xếp chọn (Selection Sort). Tuy nhiên, Insertion Sort thường hiệu quả hơn với các danh sách đã gần sắp xếp.

Dưới đây là đoạn code Python mẫu để sắp xếp một danh sách sử dụng thuật toán sắp xếp chèn:

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

    return arr

Ví dụ: Cho danh sách [64, 25, 12, 22, 11]. Sử dụng thuật toán sắp xếp chèn, ta có kết quả sau khi sắp xếp là [11, 12, 22, 25, 64].

arr = [64, 25, 12, 22, 11]
sorted_arr = insertion_sort(arr)
print(sorted_arr) # Kết quả là [11, 12, 22, 25, 64]