Radix sort gives wrong answer by changing just one loop of count subroutine

Question

It seems a very trivial problem but after a lot of thinking I still can't figure it out. I worte these two codes for Radix sort.

Code 1

#include <stdio.h>
#include <malloc.h>

#define BUCKET_SIZE 10

void prin(int* arr,int n)
{
    int i;
    for(i=0;i<n;i++)
        printf("%d ",*(arr+i));
    printf("\n");
}

int maxi(int* arr,int n)
{
    int i,max=0;
    for(i=0;i<n;i++)
    {
        if(arr[i]>max)
            max=arr[i];
    }
    return max;
}

int* count(int *arr,int n,int k)
{
    int* count,i,index;
    int* output;
    count=(int*)calloc(BUCKET_SIZE-1,sizeof(int));
    output=(int*)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
    {
        index=(arr[i]/k)%10;
        count[index]++;
    }

    for(i=0;i<BUCKET_SIZE;i++)
        count[i]+=count[i-1];

    for(i=n-1;i>=0;i--)
    {
        index=(arr[i]/k)%10;
        output[count[index]-1]=arr[i];
        count[index]--;
    }
    return output;
}

int* radixsort(int* arr,int n)
{
    int i,max,k=1;
    max=maxi(arr,n);
    while(max>0)
    {
        max/=10;
        arr=count(arr,n,k);
        k=k*10;
    }
    return arr;
}

void main()
{
    int n,i;
    scanf("%d",&n);
    int* arr;
    arr=(int*)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
        scanf("%d",(arr+i));
    arr=radixsort(arr,n);
    prin(arr,n);
}

Now if I change the sort subroutine like below, this code will not sort the given array and I can't figure why this happened, I am still traversing the whole array so and I am still calculating the right index so my elements should be filled in the right place and I should have a sorted array.

Code 2

Only count function last loop changed.

int* count(int *arr,int n,int k)
{
    int* count,i,index;
    int* output;
    count=(int*)calloc(BUCKET_SIZE-1,sizeof(int));
    output=(int*)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
    {
        index=(arr[i]/k)%10;
        count[index]++;
    }

    for(i=0;i<BUCKET_SIZE;i++)
        count[i]+=count[i-1];

    for(i=0;i<n;i++)
    {
        index=(arr[i]/k)%10;
        output[count[index]-1]=arr[i];
        count[index]--;
    }
    return output;
}

When I am doing just counting sort both functions work well. Can someone point me out where I am going wrong with radix sort, or what is the thing I am missing, and how both well in counting sort.
Thanks.

Answer 1

In your final loop in your count function, when these lines copy the contents of each "bucket", they write the last element of the output "bucket" first, followed by the next-to-last, ending with the first element:

        output[count[index]-1]=arr[i];
        count[index]--;

In the first version of your program, since you visit the elements of the input array starting at the end of the array and working your way back toward the beginning, you encounter the last element of each bucket first (and therefore put it in the last position in the output bucket), then the next-to-last element (which you put in the next-to-last position in the output), and so forth. The first element of each bucket is the last copied and is copied to the first position in the bucket.

In the second version of your program, you continue to fill in the spaces in each output bucket from back to front, but you read the input from front to back. This has the result of putting the first element of each bucket in the last position within that bucket, and the last element of the bucket in the first position. That is, each time you run the count function it reverses the order of elements within each bucket.

If you want to copy the input array reading it from front to back, you need to fill in each output bucket from front to back by using ++count[index] instead of --count[index]. You also have to start each entry of count[index] at a lower number so that you write to the correct locations.

---

Aside: your program does a lot more allocation than it needs to, and doesn't free any memory, so you have a potentially massive memory leak. You might consider passing already-allocated arrays into count instead of always allocating new ones.

Answer 2

Here is a front to back example, that also replaces the original array with a sorted array, freeing the original array. An alternative would be to do a one time allocation of a second working array, radix sort back and forth between original and working arrays, then keep the sorted array, and free the "other" array.

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

#define BUCKET_SIZE 10

void prin(int* arr, int n)
{
    int i;
    for(i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int maxi(int* arr, int n)
{
    int i,max = 0;
    for(i = 0; i < n; i++)
    {
        if(arr[i] > max)
            max = arr[i];
    }
    return max;
}

/* replaces array with sorted array, frees original array */
void count(int** parr, int n, int k)
{
    int* count, i, index;
    int* arr = *parr;
    int* output;
    int sum, cur;
    count=calloc(BUCKET_SIZE, sizeof(int));
    output=malloc(n*sizeof(int));
    for(i = 0; i < n; i++){
        index = (arr[i]/k)%10;
        count[index]++;
    }

    sum = 0;
    for(i = 0; i < BUCKET_SIZE; i++){
        cur = count[i];
        count[i] = sum;
        sum += cur;
    }

    for(i = 0; i < n; i++){
        index = (arr[i]/k)%10;
        output[count[index]++] = arr[i];
    }
    free(arr);
    free(count);
    *parr = output;
}

void radixsort(int** parr,int n)
{
    int max,k=1;
    max=maxi(*parr,n);
    while(max>0)
    {
        max/=10;
        count(parr,n,k);
        k=k*10;
    }
}

int main()
{
    int n,i;
    int* arr;
    scanf("%d",&n);
    arr = malloc(n*sizeof(int));
    for(i = 0; i < n; i++)
        scanf("%d",&arr[i]);
    radixsort(&arr,n);
    prin(arr,n);
    free(arr);
    return 0;
}