I have been looking at this for hours and can't figure this out. If the comparisons in the heapify function are changed to greater than, then the output is in increasing order as it should be. I want my list to be sorted in decreasing order though and it's not giving the correct output using the below code:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct stuff {
char *str;
}stuff_t;
void heapify(stuff_t *stuff_array, int i, int n)
{
stuff_t temp;
int left, right, max;
left = 2*i;
right = left + 1;
max = i;
if (left < n)
if (strtod(stuff_array[left].str, NULL) < strtod(stuff_array[i].str, NULL))
max = left;
if (right < n)
if (strtod(stuff_array[right].str, NULL) < strtod(stuff_array[max].str, NULL))
max = right;
if (max != i)
{
temp = stuff_array[i];
stuff_array[i] = stuff_array[max];
stuff_array[max] = temp;
heapify(stuff_array, max, n);
}
}
void heapsort(stuff_t *stuff_array)
{
short i,N;
stuff_t temp;
N = 0;
while (stuff_array[N].str)
N++;
for (i = (N/2)-1; i >= 0; i--)
heapify(stuff_array, i, N);
for (i = N-1; i >= 1; i--) {
temp = stuff_array[0];
stuff_array[0] = stuff_array[i];
stuff_array[i] = temp;
heapify(stuff_array, 0, i);
}
}
int main (int argc, char* argv[])
{
int i;
stuff_t *s_list = calloc(4, sizeof(stuff_t));
stuff_t *s_list1 = calloc(8, sizeof(stuff_t));
s_list[0].str = "9.3";
s_list[1].str = "9.3";
s_list[2].str = "7.8";
printf("before: ");
for (i = 0; i < 3; i++)
printf("%s, ", s_list[i]);
printf("\n");
heapsort(s_list);
printf("after: ");
for (i = 0; i < 3; i++)
printf("%s, ", s_list[i]);
printf("\n");
s_list1[0].str = "7.5";
s_list1[1].str = "10.0";
s_list1[2].str = "10.0";
s_list1[3].str = "8.3";
s_list1[4].str = "6.5";
s_list1[5].str = "5.0";
s_list1[6].str = "4.6";
printf("before: ");
for (i = 0; i < 3; i++)
printf("%s, ", s_list1[i]);
printf("\n");
heapsort(s_list1);
printf("after: ");
for (i = 0; i < 7; i++)
printf("%s, ", s_list1[i]);
printf("\n");
return 0;
}
program output:
// using less than comparison
before: 9.3, 9.3, 7.8,
after: 9.3, 7.8, 9.3,
before: 7.5, 10.0, 10.0,
after: 10.0, 10.0, 8.3, 7.5, 6.5, 4.6, 5.0,
// using greator than comparison
before: 9.3, 9.3, 7.8,
after: 7.8, 9.3, 9.3,
before: 7.5, 10.0, 10.0,
after: 4.6, 5.0, 6.5, 7.5, 8.3, 10.0, 10.0,