Insertion Sort (Sắp Xếp Chèn)

Đây chính là cách mà bạn thường xếp bài tây trên tay: rút một quân bài mới và chèn nó vào đúng vị trí trong những quân bài đã cầm.

Cơ Chế Hoạt Động

Giải thuật chia mảng thành:

1. Phần đã sắp xếp (Sorted Part).
2. Phần tử cần chèn (Unsorted).

Ta lần lượt lấy từng phần tử ở phần chưa sắp xếp, so sánh ngược về phía trước và chèn vào đúng chỗ.

🎬 Bubble Sort Visualizer

64

34

25

12

22

11

90

45

67

30

Chưa sắp xếp Đang so sánh Đã sắp xếp

Ví Dụ Trực Quan "Xếp Bài"

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

1. Giả sử lá bài đầu tiên 5 đã nằm đúng chỗ trên tay.
2. Rút lá 2. 2 < 5, nên chèn 2 trước 5. Tay cầm: [2, 5].
3. Rút lá 4. 2 < 4 < 5, chèn vào giữa. Tay cầm: [2, 4, 5].
4. Rút lá 6. 6 > 5, đặt cuối. Tay cầm: [2, 4, 5, 6].
5. Rút lá 1. 1 < 2, chèn đầu. Tay cầm: [1, 2, 4, 5, 6].

Code Implementation

C++

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        // Di chuyển các phần tử lớn hơn key về sau một vị trí
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Java

class InsertionSort {
    void insertionSort(int arr[]) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
}

Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Dời các phần tử lớn hơn key
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

🎓 HPN's Insight

Insertion Sort là thuật toán "vua" đối với:

1. Dữ liệu nhỏ: Nhanh hơn cả Quick Sort hay Merge Sort do không có overhead đệ quy.
2. Dữ liệu gần như đã sắp xếp (Nearly Sorted): Độ phức tạp tiệm cận O(N). Đó là lý do các thư viện chuẩn thường dùng nó làm thuật toán bổ trợ (Hybrid Sort).