Внедрение сортировки счетчиков каждый раз приводит к сбою моей программы, не может обнаружить ошибку malloc / free - PullRequest
Новая
       22

Внедрение сортировки счетчиков каждый раз приводит к сбою моей программы, не может обнаружить ошибку malloc / free

1 голос
/ 27 мая 2019

Я застрял на этом некоторое время и абсолютно не могу найти решение своей проблемы.Я следовал алгоритмам Седжвика в C, чтобы реализовать сортировку счетчиков, но по какой-то причине мой массив b неправильно считывает значения моего входного массива, а также вылетает из программы при попытке освободиться.Любая помощь будет оценена. 

void count_sort(int* a, int l, int r, int M)
{
    int i, j;
    int* cnt = (int*)malloc(M * sizeof(int));
    if (!cnt) {
        printf("Returned NULL PTR for cnt\n");
        exit(1);
    }
    int* b = (int*)malloc((r + 1) * sizeof(int));
    if (!b) {
        printf("Returned NULL PTR for b\n");
        exit(1);
    }
    printf("\n\n\n");

    for (j = 0; j < M; ++j)
        cnt[j] = 0;
    for (i = l; i <= r; ++i)
        cnt[a[i]]++;
    for (i = 1; i < M; ++i)
        cnt[i] += cnt[i - 1];

    /*
free(b);
free(cnt);
printf("Able to free here\n");
exit(0);
*/

    for (i = l; i <= r; ++i) {
        b[cnt[a[i]]] = a[i];
        printf("%d\n", b[cnt[a[i]]]);
        ++cnt[a[i]];
    }

    /*
free(b);
free(cnt);
printf("Able to free here\n");
exit(0);
*/
    for (i = l; i <= r; ++i)
        a[i] = b[i - l];

    free(cnt);
    free(b);
}

int is_sort(int* a, int N)
{
    int i;
    for (i = 0; i < N - 1; ++i) {
        if (a[i + 1] < a[i]) {
            printf("%d %d\t%d %d\n", i, a[i], i + 1, a[i + 1]);
            return 0;
        }
    }
    return 1;
}

int main(int argc, char** argv)
{

    srand(time(NULL));
    rand();

    int N = atoi(argv[1]);
    int M = atoi(argv[2]);

    int* arr = (int*)malloc(N * sizeof(int));
    int i;
    for (i = 0; i < N; ++i) {
        arr[i] = ((int)(1000 * (1.0 * rand() / RAND_MAX))) % M;
        printf("%d\n", arr[i]);
    }

    count_sort(arr, 0, N - 1, M);
    if (is_sort(arr, N))
        printf("sorted\n");
    else
        printf("not sorted");

    free(arr);
    return 0;
}

1 Ответ

2 голосов
/ 27 мая 2019

Проблема заключается в следующих строках: 


    for (i = l; i <=r; ++i) {
        b[cnt[a[i]]] = a[i];            
        printf("%d\n", b[cnt[a[i]]]);
        ++cnt[a[i]];
    }

Вы хотите уменьшить cnt[a[i]], а не увеличить, а также сделать это до назначения b[cnt[a[i]]] = a[i];, а не после.

С этими модификациями код работает правильно.

...