Подсчет сортировки отображает странное поведение

Question

Я реализовал Подсчет сортировки в задании, данном нам учителем, но иногда он не работает для больших массивов.

Вот код:

void countingSort(int *t, int n) {
    int min = findMin(t, n);
    int max = findMax(t, n);
    int range = max - min + 1;
    int *count, *output;
    int i;
    count = (int *)malloc(range * sizeof(int));
    output = (int *)malloc(n * sizeof(int));

    for (i = 0; i < range; i++) {
        count[i] = 0;
    }
    for (i = 0; i < n; i++) {
        count[t[i] - min]++;
    }
    for (i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    for (i = n - 1; i >= 0; i--) {
        output[count[t[i] - min] - 1] = t[i];
        count[t[i] - min]--;
    }
    for (i = 0; i < n; i++) {
        t[i] = output[i];
    }
}

Что не так с моим кодом?

Answer 1

Ваш код работает для небольших значений range, но может не работать, если min и max находятся слишком далеко друг от друга, в результате чего вычисления range переполняют диапазон int и malloc() сбой.

Необходимо проверить переполнение в range и проверить успешность выделения памяти. Также обратите внимание, что calloc() более подходит, чем malloc() для массива count. Наконец, вы должны освободить выделенные массивы.

Вот модифицированная версия:

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

int findMax(const int *t, int n) {
    int max = INT_MIN;
    while (n-- > 0) {
        if (max < *t) max = *t;
        t++;
    }
    return max;
}    

int findMin(const int *t, int n) {
    int min = INT_MAX;
    while (n-- > 0) {
        if (min > *t) min = *t;
        t++;
    }
    return min;
}    

int countingSort(int *t, int n) {
    int min, max, range, i;
    int *count, *output;

    if (n <= 0)
        return 0; 

    min = findMin(t, n);
    max = findMax(t, n);

    if (min < 0 && max >= 0 && (unsigned)max + (unsigned)(-min) >= INT_MAX) {
        fprintf(stderr, "countingSort: value range too large: %d..%d\n", min, max);
        return -1;
    }
    range = max - min + 1;
    if ((count = (int *)calloc(range, sizeof(int))) == NULL) {
        fprintf(stderr, "countingSort: cannot allocate %d element count array\n", range);
        return -1;
    }
    if ((output = (int *)malloc(n * sizeof(int))) == NULL) {
        fprintf(stderr, "countingSort: cannot allocate %d element output array\n", n);
        free(count);
        return -1;
    }
    for (i = 0; i < n; i++) {
        count[t[i] - min]++;
    }
    for (i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    for (i = n; i-- > 0;) {
        output[count[t[i] - min] - 1] = t[i];
        count[t[i] - min]--;
    }
    for (i = 0; i < n; i++) {
        t[i] = output[i];
    }
    free(count);
    free(output);
    return 0;
}

Вы можете избежать громоздкого и потенциально неэффективного нисходящего цикла, заменив второй и третий циклы forс этим:

    /* compute the first index for each value */
    int index = 0;
    for (i = 0; i < range; i++) {
        incr = count[i];
        count[i] = index;
        index += incr;
    }
    /* copy each value at the corresponding index and update it */
    for (i = 0; i < n; i++) {
        output[count[t[i] - min]++] = t[i];
    }