codescracker
c

C Program for Insertion Sort



« Previous Program Next Program »

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 involed 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:

// Insertion Sort Program in C
// ----codescracker.com----

#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

Print Array after each 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:

// Insertion Sort Program in C
// ----codescracker.com----

#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

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:

// Insertion Sort in C using while Loop
// ----codescracker.com----

#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

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:

// Insertion Sort in C using Function
// ----codescracker.com----

#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


« Previous Program Next Program »