This program is used for heap sort. (C++)

#include < stdlib.h>

#include < iostream.h>

#include < conio.h>

#define NUM_ITEMS 10

void heapSort(int numbers[], int array_size);

void siftDown(int numbers[], int root, int bottom);

int numbers[NUM_ITEMS];

int main()

{

clrscr();

int i;

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

numbers[i] = rand() %100 ;

cout< < "\n\nUnsorted elements are as follows::\n\n";

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

cout< < " "< < numbers[i];

heapSort(numbers, NUM_ITEMS);

cout< < "\n\nSorted elements are as follows::\n\n";

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

cout< <" "< < numbers[i];

}

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;

if (numbers[root] < numbers[maxChild])

{

temp = numbers[root];

numbers[root] = numbers[maxChild];

numbers[maxChild] = temp;

root = maxChild;

}

else

done = 1;

}

}

Related Posts by Categories