Heap Sort

 

#include<stdio.h>

#include<stdlib.h>

#include<unistd.h>

 

void swap(int * x,int *y)

{

 

int temp=*x;

*x=*y;

*y=temp;

}

 

 

 

void percDown(int a[],int i,int n)

{

int child;

int temp;

for(temp=a[i];2*i+1<n;i=child)

{

 

child=2*i;

if(child!=n-1&&a[child]<a[child+1])

child++;

if(temp<a[child])

a[i]=a[child];

else

break;

 

}

a[i]=temp;

}

void buildheap(int a[],int n)

{

int i;

for(i=n/2;i>=0;i--)

percDown(a,i,n);

 

int j;

for(j=n-1;j>=0;j--)

{

 

swap(&a[0],&a[j]);

percDown(a,0,j);

}

 

}

 

int main()

{ 

int *a,n,i;

printf("\n Enter The size of the Data To Sort\n");

scanf("%d",&n);

a=(int *)malloc(sizeof(int)*n);

for(i=0;i<n;i++)

a[i]=rand()%(n+1);

struct timeval tv_start,tv_end;

gettimeofday(&tv_start,NULL);

buildheap(a,n);

gettimeofday(&tv_end,NULL);

 

printf("\n shyam\n");

for(i=0;i<n;i++)

printf("%d ",a[i]);

printf("\n---------------------\n Time Taken is %g \n",((tv_end.tv_sec-tv_start.tv_sec)+(tv_end.tv_usec-tv_start.tv_usec)*0.000001));

return 0;

}