Principle of Insertion Sort

It works similarly to the way we sort playing cards in our hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed in the correct position in the sorted part.

It works by iterating through the array and inserting each element into its correct position in the already sorted portion of the array.

Insertion Sort

1. Start with the second element: Begin with the second element (index 1) of the array. This element is considered the key to be inserted into the sorted portion of the array.
2. Comparisons and Insertion: Compare the key with the elements in the sorted portion of the array, moving from right to left. If the current element in the sorted portion is greater than the key, shift it one position to the right to make space for the key. Repeat this process until the correct position for the key is found.
3. Insertion: Once the correct position for the key is determined, insert the key into its correct position in the sorted portion of the array.
4. Repeat: Repeat steps 2 and 3 for each subsequent element in the unsorted portion of the array until the entire array is sorted.

Code:

 #include <iostream>

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

        // Move elements of arr[0..i-1] that are greater than key
        // to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::cout << "Original array: ";
    printArray(arr, n);

    insertionSort(arr, n);

    std::cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Complexity Analysis

Time Complexity: O(n ^ 2), where n is the number of elements in the array.

• For the average and worst-case time complexity is O(n ^ 2).
• For the best case time complexity is O(n), when the array is already sorted.

Space Complexity: O(1)

• It does not require additional space proportional to the input size.