Implementing a count sort is crashing my program every time, cannot spot malloc/free error

Question

I've been stuck on this for a while and absolutely cannot find a solution to my problem. I following along Sedgewick's algorithms in C to implement a count sort, but for some reason my b array is not reading the values of my input array correctly, and also crashes the program when trying to free. Any help will be appreciated.

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

Yes, I see the error now. I thought the code would build the array starting with elements at their lowest position, thanks for the feedback! — SearchingForT
– SearchingForT, Commented May 27, 2019 at 0:30

Igor · Accepted Answer · 2019-05-26 22:21:22Z

2

The issue lies in these lines:


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

You want to decrement cnt[a[i]], not increment and also you want to do it before the assignment b[cnt[a[i]]] = a[i];, not after.

With these modifications the code works correctly.

answered May 26, 2019 at 22:21

Igor

3842 silver badges8 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Implementing a count sort is crashing my program every time, cannot spot malloc/free error

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related