Tuesday 24 January 2012

Heap sort


/*Author-Neelkant.S.Patil,GMIT,Davanagere*/
#include<stdio.h>
#include<conio.h>
#include<time.h>


#define false 0
#define true 1


void adjust(int h[],int i,int n)
{
int k,v,j,heap;
k=i;
v=h[k];
heap=false;
while(!heap && 2*k<=n)
{
j=2*k;
if(j<n)
{
if(h[j]<h[j+1])
j++;
}
if(v>=h[j])
heap=true;
else
{
h[k]=h[j];
k=j;
}
      delay(100);


}
h[k]=v;
}




void heapify(int h[],int n)
{
int i;
for(i=n/2;i>=1;i--)
adjust(h,i,n);
}




void maxdeletion(int h[],int n)
{
int i,t;
for(i=n;i>=2;i--)
{
       t=h[i];
h[i]=h[1];
h[1]=t;
adjust(h,1,i-1);
}
}




void heapsort(int h[],int n)
{


heapify(h,n);
maxdeletion(h,n);
}




void main()
{
int h[20],i,j,k;
clock_t begin,end;
int n;
clrscr();
printf("enter the value of n \n");
scanf("%d",&n);
printf("enter %d no to be sorted \n",n);
for(i=1;i<=n;i++)
scanf("%d",&h[i]);
printf("ele before sorting\n");
for(i=1;i<=n;i++)
printf("%d\n",h[i]);
begin=clock();
heapsort(h,n);
end=clock();
printf("ele after sorting \n");
for(i=1;i<=n;i++)
printf("%d\n",h[i]);
printf("total nunber of clock tick=%d\n",(end-begin));
printf("total time requier=%f\n",((end-begin)/CLK_TCK));
getch();
}

No comments:

Post a Comment