Thuật toán Insertion Sort (Sắp xếp chèn)

Kỹ thuật sắp xếp này tương tự sắp xếp bài tay: lấy từng phần tử và dời các phần tử khác để chèn phần tử đó vào vị trí đúng trong dãy đã sắp xếp.

Độ phức tạp Insertion Sort

• Time Complexity: O(n) trường hợp tốt, O(n²) trung bình và xấu
• Space Complexity: O(1)

Input và Output

Input: Danh sách chưa sắp xếp: 9 45 23 71 80 55
Output: Mảng trước sắp xếp: 9 45 23 71 80 55
Mảng sau sắp xếp: 9 23 45 55 71 80

Thuật toán

insertionSort(array, size)
Input: Mảng dữ liệu, tổng số phần tử
Output: Mảng đã sắp xếp

Begin
  for i := 1 to size-1 do
    key := array[i]
    j := i
    while j > 0 AND array[j-1] > key do
      array[j] := array[j-1]
      j := j - 1
    done
    array[j] := key
  done
End

Ví dụ (C++)

#include <iostream>
using namespace std;

void display(int *array, int size) {
    for(int i = 0; i < size; i++) cout << array[i] << " ";
    cout << endl;
}

void insertionSort(int *array, int size) {
    int key, j;
    for(int i = 1; i < size; i++) {
        key = array[i];
        j = i;
        while(j > 0 && array[j-1] > key) {
            array[j] = array[j-1];
            j--;
        }
        array[j] = key;
    }
}

int main() {
    int n; cout << "Nhập số phần tử: "; cin >> n;
    int arr[n];
    cout << "Nhập phần tử:" << endl;
    for(int i = 0; i < n; i++) cin >> arr[i];
    cout << "Trước sắp xếp: "; display(arr, n);
    insertionSort(arr, n);
    cout << "Sau sắp xếp: "; display(arr, n);
}

Kết quả

Nhập số phần tử: 6
Nhập phần tử: 9 45 23 71 80 55
Trước sắp xếp: 9 45 23 71 80 55
Sau sắp xếp: 9 23 45 55 71 80

Đặc điểm: Insertion Sort ổn định, in-place, hiệu quả cho mảng nhỏ hoặc gần như đã sắp xếp (gần O(n)). Thường dùng trong Hybrid Sort (như Timsort) cho mảng con nhỏ.