C Program for Insertion Sort

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

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

C Insertion Sort

Let's go through the insertion-sort program first. Later on, I'll explain each and every step involved in this program. The question is, "Write a program in C that sorts any given array in ascending order using the 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;
}

Because the above program was written in the Code::Blocks IDE, you will receive the following output after a successful build and run. Here is the first snapshot of the sample run:

c insertion sort

Now supply the size of the array, say 5, and enter any 5 array elements. And then press the 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

After each Insertion Sort, print the array

If you want to see the step-by-step array after each sorting on the output screen, then you can modify the above program with the following 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 the 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 the while loop

Let's create another program that also sorts any given array in ascending order as per the insertion sort technique. Here we have used the while loop to shorten 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 the sample run:

c program insertion sort

C Insertion Sort with Function

Let's create a function that takes any two arguments (an array and its size) and sorts that array in ascending order as per the insertion sort technique. Here is the program that works the 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 the start of the program, that is, before the main() function. This function accepts any two arguments, the first of which is the array and the second of which is its size. We have defined the function so that after calling the function, the 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

The same program in different languages

C Quiz


« Previous Program Next Program »


Liked this post? Share it!