CODEWITHSUNDEEP
csorting
user3666471
user3666471

Reputation: 945

Counting sort not working as expected

I'm trying to implement counting sort as given the CLRS book. My code looks like this:

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

void counting_sort(int numbers[], int k, int len)
{
    int *temp = malloc(k*sizeof(int));
    int *res = malloc(len*sizeof(int));
    int i;
    for(i = 0; i < k; i++)
    {
        temp[i] = 0;
    }

    for(i = 0; i < len; i++)
    {
        temp[numbers[i]]++;
    }

    for(i = 1; i < k; i++)
    {
        temp[i] += temp[i-1];
    }


    int j;
    for(i = len-1; i >= 0; i--)
    {
        res[temp[numbers[i]]] = numbers[i];
        temp[numbers[i]]--;
    }

    for(j = 0; j < len; j++)
        printf("%d ", res[j]);
    printf("\n");


    free(temp);
    free(res);
}

void main()
{
    int numbers[] = {2, 5, 3, 0, 2, 3, 0, 3};
    counting_sort(numbers, 6, 8);
}

But the output I get is: 0 0 0 2 2 3 3 3. The output is almost correct, I should get 0 0 2 2 3 3 3 5.

Any idea what is wrong? I have a feeling it's the last loop that's messing it up.

Upvotes: 0

Views: 144

Answers (1)

pezy
pezy

Reputation: 1090

This line is wrong:

res[temp[numbers[i]]] = numbers[i];

changed it to this:

res[temp[numbers[i]]-1] = numbers[i];

It seem to work fine.

Upvotes: 3

Related Questions