Heapsort Implementation (Inspired by the Pseudo-codes from the CLRS Book of MIT Press)

#define SIZE 10

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <math.h>

void maxHeapify(int array[], int i);

void printArray(int array[]);

void buildMaxHeap(int array[]);

void heapSort(int array[]);

int largest = 0;

int heapSize = 0;

int main(void){

int i;
int array[SIZE];

heapSize = sizeof(array) / sizeof(*(array));

srand(time(NULL));

for(i=0; i<SIZE; i++) {

array[i]=rand() % 90 + 10;

}

heapSort(array);

printf(" main() - Sorted Array: ");

for(i=0; i<SIZE; i++) {

printf("%d ", array[i]);

}

return 0;

}

void printArray(int array[]) {

int i;

for (i=0; i<SIZE; i++) {

printf("%d ", array[i]);

}

printf("\n");

}

int left(int i) {

if (i == 0){

printf(" left(): PARENT:%d has LEFT:%d\n",i,1);

return 1;

} else {

printf(" left(): PARENT:%d has LEFT:%d\n",i,2*i);

return 2*i;

}

}

int right(int i) {

if (i == 0){

printf(" right(): PARENT:%d has RIGHT:%d\n",i,2);

return 2;

} else {

printf(" right(): PARENT:%d has RIGHT:%d\n",i,2*i+1);

return 2*i+1;

}

}

int parent(int i) {

return floor((i-1)/2);

}

void maxHeapify(int array[], int i) {

int l = left(i);

int r = right(i);

if ((l <= heapSize) && (array[l] > array[i])){

largest = l;

} else {

largest = i;

}

if ((r <= heapSize) && (array[r] > array[largest])){

largest = r;

}

if (largest != i) {

int temp = array[largest];

array[largest] = array[i];

array[i] = temp;

maxHeapify(array, largest);

}

}

void buildMaxHeap(int array[]) {

int i = 0;

for (i = floor(heapSize/2); i >= 0; i--) {

maxHeapify(array, i);

}

}

void heapSort(int array[]) {

buildMaxHeap(array);

int i = 0;

for (i = heapSize; i >= 1; i--) {

int temp = array[i];

array[i] = array[0];

array[0] = temp;

heapSize = heapSize - 1;

maxHeapify(array, 0);

printArray(array);

}

}