Heap sort program in C language?

Answer 1

#include <stdlib.h>

#include <stdio.h>

#define uint unsigned int

typedef int (*compare_func)(int, int);

void heap_sort(int This[], compare_func func_pointer, uint len)

{

/* heap sort */

uint half;

uint parents;

if (len <= 1)

return;

half = len >> 1;

for (parents = half; parents >= 1; --parents)

{

int tmp;

int level = 0;

uint child;

child = parents;

/* bottom-up downheap */

/* leaf-search for largest child path */

while (child <= half)

{

++level;

child += child;

if ((child < len) &&

((*func_pointer)(This[child], This[child - 1]) > 0))

++child;

}

/* bottom-up-search for rotation point */

tmp = This[parents - 1];

for (;;)

{

if (parents child)

break;

if ((*func_pointer)(tmp, This[child - 1]) <= 0)

break;

child >>= 1;

--level;

}

/* rotate nodes from parents to rotation point */

for (;level > 0; --level)

{

This[(child >> level) - 1] =

This[(child >> (level - 1)) - 1];

}

This[child - 1] = tmp;

} while (--len >= 1);

}

#define ARRAY_SIZE 250000

int my_array[ARRAY_SIZE];

void init()

{

int indx;

for (indx=0; indx < ARRAY_SIZE; ++indx)

{

my_array[indx] = rand();

}

}

int cmpfun(int a, int b)

{

if (a > b)

return 1;

else if (a < b)

return -1;

else

return 0;

}

int main()

{

int indx;

init();

heap_sort(my_array, cmpfun, ARRAY_SIZE);

for (indx=1; indx < ARRAY_SIZE; ++indx)

{

if (my_array[indx - 1] > my_array[indx])

{

printf("bad sort\n");

return(1);

}

}

return(0);

}