I'm fairly new to algorithms, but i am working on heap sorting strings. The output should be
a
b
c
d
e
but instead it is
a
e
b
d
c
I am only using characters in the string array for testing currently, i will place full strings in once i figure out my problem. Can anyone give me some insight to my problem?
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char * string;
void siftDown(string strs[], int root, int bottom);
void heapSort(string strs[], int array_size);
int main(int argc, char *argv[])
{
int varcount = 5;
string strs[5];
int i;
strs[0] = "c";
strs[1] = "d";
strs[2] = "e";
strs[3] = "b";
strs[4] = "a";
heapSort(strs, varcount);
for(i = 0;i < varcount;++i)
printf("%s\n", strs[i]);
return 0;
}
void heapSort(string strs[], int array_size)
{
int i;
string temp[1];
for (i = (array_size / 2); i >= 0; i--)
siftDown(strs, i, array_size - 1);
for (i = array_size-1; i >= 1; i--)
{
temp[0] = strs[0];
strs[0] = strs[i];
strs[i] = temp[0];
siftDown(strs, 0, i-1);
}
}
void siftDown(string strs[], int root, int bottom)
{
int done, maxChild;
string temp[1];
done = 0;
while ((root*2 <= bottom) && (!done))
{
if (root*2 == bottom)
maxChild = root * 2;
else if (strcmp(strs[root * 2], strs[root * 2 + 1]) >> 0)
maxChild = root * 2;
else
maxChild = root * 2 + 1;
if (strcmp(strs[root], strs[maxChild]) << 0)
{
temp[0] = strs[root];
strs[root] = strs[maxChild];
strs[maxChild] = temp[0];
root = maxChild;
}
else
done = 1;
}
}
Any help would be much appreciated
My hypothesis is its something with the string compares, because it works for integers.