Insertion Sort in C

Insertion Sort, a straightforward and effective sorting technique, progressively constructs the sorted array by individually placing each element in its proper position.

 Here's a detailed overview of the algorithm, its time complexity, space complexity, and an Example implementing it:

Algorithm:

Start with the second element (index 1) and compare it with the elements to its left.

Insert the element into its correct position among the already sorted elements to its left.

Repeat steps 1 and 2 for the remaining elements, gradually expanding the sorted portion of the array.

Time Complexity:

In its best-case scenario, Insertion Sort exhibits linear time complexity of O(n) when the array is pre-sorted.

Average Case: O(n^2) - When the array is randomly ordered.

Worst Case: O(n^2) - When the array is sorted in reverse order.

Space Complexity:

Insertion Sort optimally organizes arrays in place, eliminating the need for supplementary memory, as it operates exclusively within the confines of the original array.

Example:

// Program for Insertion sort in C
#include<stdio.h> 

void insertionSort(int arr[], int k) {
    int s, key, w;
    for (s = 1; s < k; s++) {
        key = arr[s];
        w = s - 1;
        while (w >= 0 && arr[w] > key) {
            arr[w + 1] = arr[w];
            w = w - 1;
        }
        arr[w + 1] = key;
    }
}

void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

Output:

Original array: 
12 11 13 5 6 
Sorted array: 
5 6 11 12 13