Radix Sort showing wrong values in the output-CodePudding

I am learning dsa and I tried to implement radix sort in c. I used this tutorial from programiz. I implemented it but the array of numbers they are using get sorted correctly but when I used a different array it shows some garbage value.

When I insert this
int array[] = {121, 432, 564, 23, 1, 45, 788};
The output is "1 23 45 121 432 564 788" output
But When I insert this
int array[] = {3,4,1,5,2};
The output is "1 2 3 4 2496" output

I implemented the code as it is from the tutorial. Can any one point out the issue

#include <stdio.h>

void radix_sort(int array[], int size);
void counting_sort(int array[], int size, int place);

int main(void)
{
    int array[] = {3,4,1,5,2};
    int size = sizeof(array) / sizeof(int);

    radix_sort(array, size);

    for (int i = 0; i < size; i  )
        printf("%i ", array[i]);
    printf("\n");
}

void radix_sort(int array[], int size)
{
     int max = array[0];
     for (int i = 1; i < size; i  )
     {
         if (array[i] > max)
         max = array[i];
     }

for (int place = 1; max / place > 0; place *= 10)
    counting_sort(array, size, place);
}

void counting_sort(int array[], int size, int place)
{
    int output[size   1];
    int max = (array[0] / place) % 10;

    for (int i = 1; i < size; i  )
    {
         if (((array[i] / place) % 10) > max)
             max = array[i];
    }
    int count[max 1];

    for (int i = 0; i < max;   i)
        count[i] = 0;

    for (int i = 0; i < size; i  )
        count[(array[i] / place) % 10]  ;

    for (int i = 1; i < 10; i  )
        count[i]  = count[i - 1];

    for (int i = size-1; i >= 0; i--)
    {   
       output[count[(array[i] / place) % 10] - 1] = array[i];
       count[(array[i] / place) % 10]--;
    }

    for (int i = 0; i < size; i  )
       array[i] = output[i];
 }

CodePudding user response：

for (int i = 1; i < 10; i ) { will access the array out of bounds since count[max 1] => count[5 1] so your program has undefined behavior. It could crash or output garbage or do just about anything.

You should use i <= max in that loop:

for (int i = 1; i <= max; i  )  // use `i <= max` here
    count[i]  = count[i - 1];

You also need to zero out the memory of the variable length array count because it will contain indeterminate values after it's been created. You tried doing that with for (int i = 0; i < max; i) count[i] = 0; but that misses the last element in the array.

Either do

int count[max   1];
for (int i = 0; i <= max;   i) count[i] = 0;

int count[max   1];
memset(count, 0, sizeof count);  // include <string.h>