C Code for Heapsort algorithm

heapsort(x,n)

int x[],n;

{

int i,data,s,f,ivalue;

/* create initial heap */

for(i=1;i <>

{

data=x[i];

/* insert_heap (x,i,data); */

s=i;

f=(s - 1) / 2; /* f is the father of s */

while(s > 0 && x[f] <>

{

x[s]=x[f]; /* move up the tree */

s=f;

f=(s - 1) / 2; /* f is the father of s */

}/* end while */

x[s]=data;

}/* end for i.e. a heap has been created */

/* begin repeatedly removing the maximum element i.e. x[0], */

/* place it at the end of the array.*/

/* Convert the remaining part to a heap */

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

{

/* delete the root */

ivalue=x[i];

x[i]=x[0]; /* the root is placed at the bottom */

f=0;

/* begin adjusting the heap by pushing the element x[i] i.e. ivalue */

if(i == 1)

s=-1;/* no further processing required */

else

s=1;

if(i > 2 && x[2] > x[1])

s=2;

while(s >=0 && ivalue <>

{

/* push ivalue down the heap */

x[f]=x[s];

f=s;

/* s=largeson(f, i-1) */

s=2*f +1; /* s is the child of f */

if(s+1 <= i-1 && x[s] <>

s=s+1; /* select the larger of the two children of f i.e. 2j + 1 or 2j + 2 */

if(s > i-1) /* when bounds have been reached */

s=-1;

}/* end while */

/* insert ivalue at fth location */

x[f]=ivalue;

}/* end for */

}/* end heap sort */