C Program for Insertion Sort

In this tutorial, we will learn about how to create a program in C that sorts an array in ascending order using insertion sort technique. Here we have also created a function that can be used to sort any given array (by user at run-time) as per insertion sort technique in ascending order.

But before going through the program, if you are not aware about how a insertion sort actually works, then I recommend you to go through the step by step working of Insertion Sort. Let's move on and implement it in a C program.

Insertion Sort in C

Let's go through the insertion sort program first. Later on, I'll explain each and every steps involved in this program. The question is, Write a program in C that sorts any given array in Ascending order using insertion sort technique. The answer to this question is:

#include<stdio.h>
#include<conio.h>
int main()
{
    int arr[50], size, i, j, k, element, index;
    printf("Enter Array Size: ");
    scanf("%d", &size);
    printf("Enter %d Array Elements: ", size);
    for(i=0; i<size; i++)
        scanf("%d", &arr[i]);
    for(i=1; i<size; i++)
    {
        element = arr[i];
        if(element<arr[i-1])
        {
            for(j=0; j<=i; j++)
            {
                if(element<arr[j])
                {
                    index = j;
                    for(k=i; k>j; k--)
                        arr[k] = arr[k-1];
                    break;
                }
            }
        }
        else
            continue;
        arr[index] = element;
    }
    printf("\nSorted Array:\n");
    for(i=0; i<size; i++)
        printf("%d ", arr[i]);
    getch();
    return 0;
}

As the above program was written under Code::Blocks IDE, therefore after successful build and run, you will get the following output. Here is the first snapshot of the sample run:

c insertion sort

Now supply size for the array say 5 and enter any 5 array elements. And then press ENTER key to sort that array. Here is the second snapshot of the sample run:

insertion sort in c

Let's take another sample run. Here is the final snapshot of the sample run:

c program sort array insertion sort

Program Explained

  • Receive size for an array and then receive elements of that size
  • That is, if user supplied 5 as array size, then ask him/her to enter any 5 elements for that array
  • Create a for loop that runs from 1 to one less than the size of the array
  • Inside the loop, initialize the current element, that is element present at ith index of the array to any variable say element
  • Use if statement to check whether the current element is less than the previous element or not
    • If it is, then program flow goes inside the if block
    • Inside the if block, create another for loop that runs from start (0) to less than or equal to the value of i (outer loop variable)
    • Inside this loop, check whether the value of element is less than the value of arr[j] or not
    • If it is, then initialize the current index to a variable say index and push all the element to its next index one by one using for loop
    • That is create a for loop that starts from the value of i and runs until it is greater than the value of j (outer loop variable)
    • Never forgot to use break keyword to break out of the for loop
  • And if the statement of if's condition evaluates to be false, then use continue keyword to tell the compiler to go back to the outer for loop. That is increment its variable and continue to do the same process as told above
  • After performing this and continue to increment the first for loop variable (i), initialize the value of element variable at arr[index]
  • For example, if user has supplied 1 5 2 4 3 as array
  • Therefore, at first run of for loop
  • The loop variable i is initialized to 1 and i<size or 1<5 evaluates to be true, therefore program flow goes inside the loop
  • The value at arr[i] or arr[1] or 5 gets initialized to element
  • And element<arr[i-1] or 5<arr[0] or 5<1 evaluates to be false, therefore program flow goes to else block, and using continue keyword program flow goes back to the first for loop
  • That is, there was no any swapping gets placed, therefore the array is still in its original order which is 1 5 2 4 3
  • As the program flow again came back to the for loop and increments the value of i
  • Now i holds 2, and i<size or 2<5 evaluates to be true. Therefore program flow goes inside the loop again
  • Value at arr[i] or arr[2] or 2 gets initialized to element
  • And element<arr[i-1] or 2<arr[1] or 2<5 evaluates to be true, therefore program flow goes inside the if block
  • The value of j (loop variable of inner for loop) gets initialized with 0, and j<=i or 0<=2 evaluates to be true, therefore program flow goes inside the loop
  • And element<arr[j] or 2<1 evaluates to be false, therefore program flow goes back to inner for loop and increments the value of j
  • Now j holds 1 and j<=i or 1<=2 evaluates to be true. Therefore program flow goes inside the loop
  • And again element<arr[j] or 2<5 evaluates to be true, therefore program flow goes inside the if block
  • And j or 1 gets initialized to index variable. And value of i or 2 gets initialized to k (loop variable)
  • And k>j or 2>1 evaluates to be true, therefore program flow goes inside the loop and arr[k-1] or arr[1] or 5 gets initialized at arr[k] or arr[2]
  • The value of k now gets decremented and becomes 1. And k>j or 1>1 evaluates to be false
  • Therefore, program flow goes out of this loop, and found break keyword. Using this program flow exits the outer for loop (second one) and goes back to first for loop
  • Now the new array is 1 2 5 4 3
  • There the value of i again gets incremented and i<size or 3<5 evaluates to be true, therefore program flow again goes inside the loop and follow the same procedure as told above to sort the array as per insertion sort technique

Print Array after each Insertion Sort

If you want to see the step by step array after each sorting on output screen, then you can modify the above program with below one:

#include<stdio.h>
#include<conio.h>
int main()
{
    int arr[50], size, i, j, k, element, index;
    printf("Enter Array Size: ");
    scanf("%d", &size);
    printf("Enter %d Array Elements: ", size);
    for(i=0; i<size; i++)
        scanf("%d", &arr[i]);
    for(i=1; i<size; i++)
    {
        element = arr[i];
        if(element<arr[i-1])
        {
            for(j=0; j<=i; j++)
            {
                if(element<arr[j])
                {
                    index = j;
                    for(k=i; k>j; k--)
                        arr[k] = arr[k-1];
                    break;
                }
            }
        }
        else
            continue;
        arr[index] = element;
        printf("\nStep %d: ", i);
        for(j=0; j<size; j++)
            printf("%d ", arr[j]);
        printf("\n");
    }
    printf("\nSorted Array:\n");
    for(i=0; i<size; i++)
        printf("%d ", arr[i]);
    getch();
    return 0;
}

Here is the final snapshot of sample run:

insertion sort program in c

Here is another final snapshot of another sample run:

c insertion sort program

Insertion Sort in C using while Loop

Let's create another program that also sorts any given array in ascending order as per insertion sort technique. Here we have used while loop to short the code:

#include<stdio.h>
#include<conio.h>
int main()
{
    int arr[5], i, j, elem;
    printf("Enter any 5 array elements: ");
    for(i=0; i<5; i++)
        scanf("%d", &arr[i]);
    for(i=1; i<5; i++)
    {
        elem = arr[i];
        j = i-1;
        while((elem<arr[j]) && (j>=0))
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = elem;
    }
    printf("\nSorted Array in ascending order:\n");
    for(i=0; i<5; i++)
        printf("%d ", arr[i]);
    getch();
    return 0;
}

Here is the final snapshot of sample run:

c program insertion sort

Insertion Sort in C using Function

Let's create a function that takes any two argument (array and its size) to sort that array in ascending order as per insertion sort technique. Here is the program that works same as above except that here we have created a function that performs sorting:

#include<stdio.h>
#include<conio.h>
void insertsort(int arr[], int size);
int main()
{
    int arr[50], size, i;
    printf("How many element you want to store? ");
    scanf("%d", &size);
    printf("Enter any %d array elements: ", size);
    for(i=0; i<size; i++)
        scanf("%d", &arr[i]);
    insertsort(arr, size);
    printf("\nSorted Array in ascending order:\n");
    for(i=0; i<size; i++)
        printf("%d ", arr[i]);
    getch();
    return 0;
}
void insertsort(int arr[], int size)
{
    int i, elem, j;
    for(i=1; i<size; i++)
    {
        elem = arr[i];
        j = i-1;
        while((elem<arr[j]) && (j>=0))
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = elem;
    }
}

As you can see from the above program, we have declared a function at start of the program, that is before main() function. This function takes any two argument, first is the array and second is for its size. We have defined the function so that after calling the function, program successfully performs the action as defined in the function definition. Here is the final snapshot of the sample run:

c insertion sort using function

Same Program in Other Languages

C Online Test


« Previous Program Next Program »



Like/Share Us on Facebook 😋