C Program to implement Insertion Sort Algorithm

Algorithms are backbone of programs and they are studied deeply by computer science students. Each algorithm can perform a specific task. Sometimes we have to choose a specific and better performing algorithm out of many similar functioning algorithms.

In this article, I will demonstrate implementation of a sorting algorithm called Insertion Sort. This program is written using Dev-C++ compiler version 4.9.9.2 installed on a windows 7 64-bit machine.

Since the nature of problem is advanced, the article is for intermediate to advanced C learners.

Problem Definition

Given an array of unsorted numbers, this algorithm sort them in ascending or descending order. To discuss the merit and demerit of this algorithm is not in the scope of this article.
The program ask total number of elements and the elements from user and keep them in an array.
To sort the array it uses a ‘temp’ variable to store each element of array temporarily.

Insertion Sort Algorithm
Insertion Sort Algorithm

From the above figure, you can see that all numbers before temp are sorted because whenever a temp is selected it is compared with all the numbers to its left and inserted in its proper place. All numbers in the right of temp are unsorted and need to be traversed one-by-one.

Flowchart – Insertion Sort Algorithm

Flowchart - C Program to Implement Insertion Sort Algorithm
Flowchart – C Program to Implement Insertion Sort Algorithm

 

Program Code – Insertion Sort Algorithm

/* C Program to Implement Insertion Sort Algorithm */

#include <stdio.h>

main()
{

    int n,array[20],temp,i,j;

    printf("Enter the number of elements to enter:");
    scanf("%d",&n);


/* enter elements into the array */

    for(i=0;i<n;i++) {
        printf("Enter the element in to the array:");
        scanf("%d",&array[i]);
}

    for(i=1;i<n;i++) {
        j = i;
        while(j > 0 && array[j] < array[j-1]) {

            temp = array[j];
            array[j]= array[j-1];
            array[j-1] = temp;
            j--;
        }
    }

    for(i=0;i<n;i++) {
        printf("%d\t",array[i]);
        }

system("PAUSE");
return 0;
}

Output

Output - Implementing Insertion Sort Algorithm
Output – Implementing Insertion Sort Algorithm
Advertisements