Insertion Sort – C Program

//**********************************************************
// Insertion Sorting Algorithm Implementation & Analysis.
//**********************************************************

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<conio.h>
#include<dos.h>
#define SIZE 25000

void sorting(void);

int x[SIZE];
void main()
{
int i;
clrscr();

//Best-Case(Ascending Order)
for(i=0;i<SIZE;i++)
x[i]=i;

printf(“\n**** Best Case ****\n”);
sorting();

//Average-Case(Random Order)
randomize();
for(i=0;i<SIZE;i++)
x[i]=random(SIZE);

printf(“\n\n**** Average Case ****\n”);
sorting();

//Worst-Case(Descending Order)
for(i=SIZE;i>=0;i–)
x[i]=(SIZE-i);

printf(“\n\n**** Worst Case ****\n”);
sorting();

getch();
}

void sorting()
{
int i,k,y;
long int count=0;
clock_t start, end;
start = clock();

/*
Initially x[0] may be thought of as a sorted file of
one element. After each repetition of the following
loop, the element x[0] through x[k] are in order.
*/
for(k=1;k<SIZE;k++)
{
//Insert x[k] into the sorted file
y=x[k];

//Move down 1 position all elements greater than y
for(i=k-1;i>=0 && y<x[i];i–)
{
x[i+1]=x[i];
count++;
}

//Insert y at proper position
x[i+1]=y;
}

end = clock();
printf(“The time was: %f\nNo.of Shifts: %ld”, (end – start) / CLK_TCK,count);
}