Friday, January 13, 2012

Sorting Algorithm :: Heap sort

#include<stdio.h>
#include<math.h>


int h,arr_size;


void maxheap_property(int a[],int i)
{
int l,r,largest,temp;
l=2*i+1; r=2*i+2;


if(l<h && a[l]>a[i]) largest=l;
else  largest=i;


if(r<h && a[r]>a[largest]) largest=r;
if(largest!=i)
{
temp=a[i];
a[i]=a[largest];
a[largest]=temp;
maxheap_property(a,largest);
}
}
void build_maxheap(int a[])
{
int i,j;
h=arr_size;
j=floor((arr_size/2));
for(i=j-1;i>=0;i--)
maxheap_property(a,i);
}
void heap_sort(int a[])
{
int i,temp;


build_maxheap(a);
for(i=arr_size-1;i>=1;i--)
{
temp=a[0];
a[0]=a[i];
a[i]=temp; h--;
maxheap_property(a,0);
}
}


int main()
{
int i,n,a[50];


printf("How many numbers: ");
while(scanf("%d",&n) == 1)
{
        arr_size=n;
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        heap_sort(a);


        for(i=0;i<n;i++)
            printf("%d ",a[i]);
}
return 0;
}

No comments:

Post a Comment