views:

74

answers:

1

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,
+4  A: 

You cannot use i*2 and i*2+1 as addresses for children if you start counting from 0. The problem is that 2*0 = 0 (left child will be the same as the parent).

6502
What should the children be in this case?
The children are i*2+1 and i*2+2 when using 0-indexing.
Justin Peel