Thuật Toán Sắp Xếp Chèn (Insertion Sort)

Phân loại: Giải thuật sắp xếp ổn định.

Cấu trúc dữ liệu: Ngẫu nhiên.
Độ phức tạp thời gian (Time Complexity): Trường hợp xấu nhất (Worst Case) O(n²).

Độ phức tạp dung lượng (Space Complexity): O(1).

Độ phức tạp bộ nhớ (Memory Complexity): O(1).

Giải thích thuật toán sắp xếp chèn (Insertion Sort):

Thuật toán sắp xếp chèn là một thuật toán sắp xếp đơn giản, hoạt động theo cách sau:

1. Bắt đầu từ phần tử đầu tiên của mảng (coi như đã được sắp xếp).
2. Lấy phần tử tiếp theo và chèn nó vào vị trí đúng trong phần đã sắp xếp.
3. Lặp lại bước 2 cho đến khi toàn bộ mảng đã được sắp xếp.

Pseudocode:

procedure insertionSort(A : mảng cần sắp xếp)
    for i từ 1 đến độ dài của A - 1 làm
        key := A[i] // Gán giá trị của phần tử hiện tại vào biến key
        j := i - 1 // Khởi tạo chỉ số j là chỉ số của phần tử trước đó trong mảng
        while j >= 0 và A[j] > key là đúng là
            A[j + 1] := A[j] // Di chuyển phần tử A[j] sang phải một vị trí
            j := j - 1 // Giảm chỉ số j để di chuyển đến phần tử trước đó trong mảng
        A[j + 1] := key // Gán giá trị của key vào vị trí thích hợp trong mảng đã sắp xếp
    kết thúc vòng lặp
end procedure
 

Code C++:

#include <iostream>

using namespace std;

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ử của arr[0..i-1], lớn hơn key, lên một vị trí phía trước

        while (j >= 0 && arr[j] > key) {

            arr[j + 1] = arr[j];

            --j;

        }

        arr[j + 1] = key;

    }

}

int main() {

    int arr[] = {12, 11, 13, 5, 6};

    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    for (int i = 0; i < n; ++i) {

        cout << arr[i] << " ";

    }

    return 0;

}