Algorithms are the 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 the 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.
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
Program Code
/* 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
Enter the number of elements to enter:8
Enter the element in to the array:4
Enter the element in to the array:35
Enter the element in to the array:66
Enter the element in to the array:55
Enter the element in to the array:3
Enter the element in to the array:55
Enter the element in to the array:23
Enter the element in to the array:12
3 4 12 23 35 55 55 66