Độ phức tạp Insertion Sort trên mảng đặc biệt C++

Độ phức tạp Insertion Sort

• Best case (đã sắp xếp): O(n)
• Average/Worst case: O(n²)

Mảng dạng đặc biệt: 6, 5, 8, 7, 10, 9... (cặp hoán vị)

Mảng này chỉ có các cặp liền kề bị hoán vị. Insertion sort chỉ cần 1 phép đổi chỗ cho mỗi cặp → O(n).

Code Insertion Sort

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int element = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > element) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = element;
    }
}