Insertion Sort program in C - and how it works

Insertion sort algorithm works well for smaller arrays. Like selection sort and bubble sort, it involves two loops, so it may not be a good choice for sorting larger arrays with thousands of elements or more.

How it works

Insertion Sort in C

Here is a program written in C language that sorts a give array using the Insertion sort algorithm.

#include <stdio.h>

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

void insertionSort(int arr[], int n) {
    int i, j, temp;

    for(i=1; i<n; i++) {
        j=i-1;
        temp=arr[i];
        while(j>=0 && arr[j]>temp) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1]=temp;
    }
}

int main() {
    int arr[] = {325, 135, 25, 1025, 68, 17, 512, 468};
    int length;
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Size of the array is %d\n", n);
    printf("Here is the array before sorting:\n");
    printArray(arr, n);
    insertionSort(arr, n);
    printf("Here is the sorted array:\n");
    printArray(arr, n);
    return 0;
}

How the program works

The function insertionSort() is quite simple. It receives the array and its size as arguments. The inner while loop is used to move the larger elements towards the right one-by-one, so as to make room to insert the current element at the correct position. The actual assignment operation arr[j+1] = temp happens outside the while loop to minimise the number of assignment operations.