Insertion Sort Program In C Language

What is an Insertion Sort

Insertion Sort works like a cards game. If the next value is greater than the previous element then the value goes to the right side of the element, else it moves to the left side of the element. In the same way, the array will be sorted.

We can say that insertion sort works by placing an element at its correct position in sorted part of the array.

You Can Learn in Depth about Insertion Sort Algorithm from here.

Algorithm for Insertion Sort in C Language

• We iterate over the array from arr[1] to arr[n - 1].
• In each iteration, we compare the current element to its predecessor.
• If the current element is smaller than its predecessor, compare it to the elements before it. All the elements greater than the current element are shifted and the current element is placed at its correct position.

C Language Program For Insertion Sort:

#include <stdio.h>

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

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

int main() {
    int arr[10000];
    int n;
    printf("Enter size of the array: ");
    scanf("%d", &n);
    printf("Enter the array elements: ");
    for(int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    insertionSort(arr, n);
    printf("After sorting, the array is: ");
    printArray(arr, n);
}

Enter size of the array: 5
Enter the array elements: 0 -45 34 56 4
After sorting, the array is: -45 0 4 34 56

Time Complexity

The worst case time complexity of insertion sort in O(\(n^2\)). The best case time complexity is O(n) and the average case time complexity is also O(n).