Heap-sort Source-Code

November 27th, 2007

Filed under: Algorithms — Unggul_USA @ 2:28 pm — View blog reactions

#include
#include
#define NUM_ITEMS 100
void heapSort(int numbers[], int array_size);
void siftDown(int numbers[], int root, int bottom);
int numbers[NUM_ITEMS];
int counter;
int main()
{
int i; //seed random number generator
srand(getpid()); //fill array with random integers
for (i = 0; i < NUM_ITEMS; i++)
numbers[i] = rand();
heapSort(numbers, NUM_ITEMS); //perform heap sort on array
for (i = 0; i < NUM_ITEMS; i++)
printf("%i\n", numbers[i]);
printf("Done with sort.\n");
printf("%i %i\n", i, counter);
}

void heapSort(int numbers[], int array_size)
{
int i, temp;

for (i = (array_size / 2)-1; i >= 0; i–)
siftDown(numbers, i, array_size);
for (i = array_size-1; i >= 1; i–)
{
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i-1);
}
}

void siftDown(int numbers[], int root, int bottom)
{
int done, maxChild, temp;
done = 0;
while ((root*2 <= bottom) && (!done))
{
if (root*2 == bottom)
maxChild = root * 2;
else if (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
counter++;
if (numbers[root] < numbers[maxChild])
{
temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;
}
else
done = 1;
counter++;
}
}