Insertion Sort Algorithm

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 algorithm

 

 

Insertion Sort Complexity:

Time Complexity
Best O(n)
Worst O(n2)
Average O(n2)
Space Complexity O(1)

Recommended Articles for you: