Giới Thiệu Sắp Xếp Chèn

Sắp xếp chèn (Insertion Sort) là một thuật toán sắp xếp đơn giản, hoạt động bằng cách xây dựng một mảng đã sắp xếp từng phần tử một. Nó lấy từng phần tử từ mảng chưa sắp xếp và chèn nó vào đúng vị trí trong mảng đã sắp xếp.

Tưởng tượng bạn có một bộ bài và bạn muốn sắp xếp nó. Bạn có thể lấy từng lá bài và đặt nó vào đúng vị trí trong các lá bài đã được sắp xếp mà bạn đang giữ. Thuật toán này phù hợp với các tập dữ liệu nhỏ và có độ phức tạp thời gian là O(n^2). Nó là một phương pháp sắp xếp ổn định.

Cách Thức Hoạt Động

Chúng ta bắt đầu với một mảng chưa được sắp xếp, ví dụ: int[] data = {5, 3, 8, 1, 4};

Ban đầu, chúng ta coi phần tử đầu tiên (5) là một mảng đã được sắp xếp có một phần tử.

Lượt Sắp Xếp Đầu Tiên

Lấy phần tử thứ hai (3) và so sánh với phần tử đã sắp xếp (5). Vì 3 nhỏ hơn 5, chúng ta dịch chuyển 5 sang phải một vị trí và chèn 3 vào vị trí đầu tiên.

Mảng trở thành: {3, 5, 8, 1, 4}

Lượt Sắp Xếp Thứ Hai

Lấy phần tử thứ ba (8) và so sánh với các phần tử đã sắp xếp (3, 5). Vì 8 lớn hơn 5, nó đã ở đúng vị trí.

Mảng vẫn là: {3, 5, 8, 1, 4}

Lượt Sắp Xếp Thứ Ba

Lấy phần tử thứ tư (1) và so sánh với các phần tử đã sắp xếp (3, 5, 8).

• 1 nhỏ hơn 8, dịch chuyển 8 sang phải. Mảng tạm thời: {3, 5, 8, 8, 4}
• 1 nhỏ hơn 5, dịch chuyển 5 sang phải. Mảng tạm thời: {3, 5, 5, 8, 4}
• 1 nhỏ hơn 3, dịch chuyển 3 sang phải. Mảng tạm thời: {3, 3, 5, 8, 4}
• Đã đến đầu mảng, chèn 1 vào vị trí đầu tiên.

Mảng trở thành: {1, 3, 5, 8, 4}

Lượt Sắp Xếp Cuối Cùng

Lấy phần tử cuối cùng (4) và so sánh với các phần tử đã sắp xếp (1, 3, 5, 8).

• 4 nhỏ hơn 8, dịch chuyển 8 sang phải. Mảng tạm thời: {1, 3, 5, 8, 8}
• 4 nhỏ hơn 5, dịch chuyển 5 sang phải. Mảng tạm thời: {1, 3, 5, 5, 8}
• 4 lớn hơn 3, chèn 4 vào vị trí sau 3.

Mảng trở thành: {1, 3, 4, 5, 8}

Tối Ưu Hóa Mã Nguồn

Chúng ta có thể nhận thấy một quy luật: sử dụng một vòng lặp ngoài để duyệt qua các phần tử cần sắp xếp và một vòng lặp trong (hoặc cấu trúc tương tự) để tìm vị trí chèn thích hợp.

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int currentElement = arr[i];
            int j = i - 1;

            // Di chuyển các phần tử của arr[0..i-1], lớn hơn currentElement,
            // sang một vị trí trước vị trí hiện tại của chúng
            while (j >= 0 && arr[j] > currentElement) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = currentElement;
        }
    }
    

Trong đoạn mã trên:

• Vòng lặp ngoài for (int i = 1; i < n; i++) duyệt từ phần tử thứ hai đến cuối mảng.
• currentElement lưu trữ phần tử đang được xem xét để chèn.
• Vòng lặp while tìm vị trí chèn thích hợp bằng cách dịch chuyển các phần tử lớn hơn currentElement sang phải cho đến khi tìm thấy vị trí hoặc hết mảng con đã sắp xếp.
• Cuối cùng, currentElement được chèn vào vị trí đúng.

Sắp Xếp Chèn Nhị Phân

Một biến thể của sắp xếp chèn là Sắp xếp Chèn Nhị Phân (Binary Insertion Sort). Thay vì so sánh tuyến tính phần tử mới với các phần tử đã sắp xếp, nó sử dụng tìm kiếm nhị phân để xác định vị trí chèn, giúp giảm số lần so sánh.

Các Triển Khai Khác

Dưới đây là một số ví dụ triển khai bằng C:

    // Triển khai 1: Dạng vòng lặp đơn giản
    void insertionSortC1(int arr[], int n) {
        for (int i = 1; i < n; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }

    // Triển khai 2: Sử dụng hàm phụ
    void insertElement(int arr[], int n) {
        int key = arr[n];
        int i = n - 1;
        while (i >= 0 && arr[i] > key) {
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = key;
    }

    void insertionSortC2(int arr[], int n) {
        for (int i = 1; i < n; i++) {
            insertElement(arr, i);
        }
    }
    

Ví dụ gọi và kiểm tra:

    #include <iostream>
    #include <vector>

    // (Định nghĩa các hàm sắp xếp chèn ở trên)

    int main() {
        int data[] = {99, 2, 3, 1, 22, 88, 7, 77, 54};
        int n = sizeof(data) / sizeof(data[0]);

        insertionSortC1(data, n); // Hoặc insertionSortC2

        std::cout << "Mảng đã sắp xếp: ";
        for (int i = 0; i < n; i++) {
            std::cout << data[i] << " ";
        }
        std::cout << std::endl;

        return 0;
    }