This blog post explains Insertion Sort Algorithm and its implementation using the C programming language. So before writing the C code for the Insertion Sort Algorithm let’s first understand the Insertion Sort Algorithm.

What is Insertion Sort Algorithm:

It is a simple sorting algorithm. In this algorithm, each iteration removes one element from the input list, finds the location it belongs within the sorted list and inserts it there. It repeats until no unsorted elements remain in the input list.

Insertion sort algorithm is not much efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Insertion Sort Steps:

Let’s see the required steps to sort a list of size 'n' in ascending order using the Insertion Sort . Suppose unsorted list is int arr[n].

1. Iterate from arr[1] to arr[n] over the array.
2. Compare the current element (key) to its predecessor.
3. If the key element is smaller than its predecessor. Move the greater elements one position up to make space for the swapped element.

Insertion Sort example code:

Now let’s see the example code for the Insertion Sort using the C programming language.

#include <stdio.h>

//Function to sort an array using insertion sort
void insertionSort(int arr[], int n)
{
    int i, key, j;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;

        /*Compare key with each element on the left element and
          move it one position aheadof their current
          position if it is greater than key*/
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

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


int main()
{
    int arr[] = {11, 25, 10, 22, 64};

    //calculate array size
    int array_size  = sizeof(arr) / sizeof(arr[0]);

    //Call function to sort the array
    insertionSort(arr, array_size );

    //print sorted array
    printArray(arr, array_size );

    return 0;
}

Output:

Insertion Sort Complexity:

Recommended Articles for you:

• Bubble Sort Algorithm.
• Quickselect Algorithm.
• Merge Sort algorithm with example code.
• Quick Sort Algorithm with example code.
• Best programming laptop for programmers.
• How do you reverse an array in C?
• C program to find the Median of two sorted arrays of different sizes.
• Basics of the recursive function.
•  C program to rearrange array such that even positioned are greater than odd.
• How to rotate an array left and right by a given number K?
• Why is it faster to process sorted array than an unsorted array?
• How to access 2d array in C?
• How to remove duplicates from a given array in C?
• Array interview questions.
• How to create dynamic array in C?
• How to pass an array as a parameter in C?