I had this working in C++ but wanted to get a C version. I'm pretty sure I'm getting lost with the pointers. I would appreciate any help.
Code:#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ARRAY_SIZE 8
void swap(char** first, char** second);
void print(char **array, const int arraySize);
void heapSort(char **a);
void makeHeap(char **a);
void siftDown(char *a, int node, int size);
int main( )
{
char **someArray;
someArray = (char**)calloc(sizeof(char**),ARRAY_SIZE);
if (someArray == NULL)
{
printf("Error allocating filename array\n");
exit(1);
}
someArray[0] = "Darin";
someArray[1] = "David";
someArray[2] = "Brian";
someArray[3] = "Dog";
someArray[4] = "Nikki";
someArray[5] = "Aaron";
someArray[6] = "Robert";
someArray[7] = "Tim";
heapSort(someArray);
print(someArray, ARRAY_SIZE);
free(someArray);
system("PAUSE");
return 0;
}
void swap(char **first, char **second)
{
char *temp = *first;
*first = *second;
*second = temp;
}
void print(char **array, const int arraySize)
{
int i;
for(i = 0; i < arraySize; i++)
printf("%s\n", array[i]);
}
void siftDown(char *a, int node, int size)
{
while (2 * node + 1 < size)
{
int largest = node;
//If the child has a sibling and the child's value is less than its sibling's
if (a[largest] < a[2 * node + 1])
largest = 2 * node + 1;
if (2 * node + 2 < size &&
a[largest] < a[2 * node + 2])
largest = 2 * node + 2;
if (a[node] < a[largest])
{ //out of max-heap order
//swap(&a[node], &a[largest]);
node = largest;
}
else
break;
}
}
void makeHeap(char **a)
//This function will play a in a max-heap order.
//The shiftDown function is called.
{
int i;
for (i = ARRAY_SIZE / 2; i >= 0; --i)
siftDown(*a, i, ARRAY_SIZE);
}
void heapSort(char **a)
//This function will sort the values using heap
//sort. makeHeap and shiftDown functions are called.
{
int size;
makeHeap(a);//first place a in max-heap order
size = ARRAY_SIZE;
while (size != 1)
{//swap the root(maximum value) of the heap with the last element of the heap
swap(&a[0], &a[size - 1]);
//decrease the size of the heap by one so that the previous max value will
//stay in its proper placement
--size;
siftDown(*a, 0, size);//put the heap back in max-heap order
}
}