Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
insertion sort algorithm in c:
/************************************************************/
/* File name : InsertionSort.c */
/* Description : Performs Insertion sort */
/* Author : Sakhamo */
/* Date & version : Oct 28th 2009 */
/* Copy Right : C open source holds all rights to this */
/* code. This codes can be re-used by any */
/* individual for non commerical purpose */
/* only */
/* Tested : VC 2005, 0-errors, 0-warnings */
/************************************************************/
#define DEBUG 0
#define NO_OF_IN_SAMP 10
/* Input, assuming 10 samples */
int inp[NO_OF_IN_SAMP] = {12, 4, 36, 29, 10, 11, 3, 5, 17, -1};
/* Output, same as of input array size */
int out[NO_OF_IN_SAMP];
#include"stdio.h"
void main()
{
int S_el, Uns_el;
int i, j, cnt;
/* Insertion Sort */
for(i = 0; i < (NO_OF_IN_SAMP - 1); i++)
{
S_el = inp[i + 1];
cnt = i;
for(j = (i + 1); j > 0; j--,cnt--)
{
Uns_el = inp[j - 1];
/* Swapping, if sorted element is less than unsorted element */
if(S_el < Uns_el)
{
inp[j] = Uns_el;
inp[cnt]= S_el;
}
}
#if DEBUG
for(j = 0; j < NO_OF_IN_SAMP; j++)
printf("%d\t",inp[j]);
printf("\n");
#endif
}
printf("Sorted array:\t");
for(j = 0; j < NO_OF_IN_SAMP; j++)
printf("%d\t",inp[j]);
}
/* End of insertion sort */