Heapsort в порядке убывания не работает - PullRequest
Новая
       7

Heapsort в порядке убывания не работает

1 голос
/ 01 июля 2010

Я смотрю на это часами и не могу понять это.Если сравнения в функции heapify изменяются на больше чем, то выходные данные располагаются в порядке возрастания, как и должно быть.Я хочу, чтобы мой список сортировался в порядке убывания, и он не дает правильного вывода, используя следующий код: 

#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;
}

вывод программы: 

// 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,

1 Ответ

4 голосов
/ 01 июля 2010

Вы не можете использовать i * 2 и i * 2 + 1 в качестве адресов для детей, если начнете считать с 0. Проблема в том, что 2 * 0 = 0 (левый ребенок будет таким же, как родитель).

...