Radix sort not sorting "some" numbers?

Question

I'm trying to implement Radix sort, from all i learnt is that it first compares the one's digit , places in the right order, the it goes for ten's so on and so fourth.

i tried to implement it but didn't got satisfactory results, what i'm doing wrong here? Here is my code:

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

struct heap {
    int data;
};

int main()
{
    int arr[18] = {545, 934, 829, 883, 842, 957, 241, 856, 878, 101, 555, 20, 964, 529, 156, 161, 566, 820};
    int i;

    struct heap *heaparr = malloc(sizeof(struct heap) * 18);

    for(i=0; i<18; i++) {
        heaparr[i].data = arr[i];
    }

    int k = 0, temp, div = 1;
    int ind = 0;

    while(div<=100 ){
        k=0;
        ind = 0;
        while(k<10) {
            for(i=0; i<18; i++) {
                if ((heaparr[i].data/div)% 10 == k) {
                    temp = heaparr[ind].data;
                    heaparr[ind].data = heaparr[i].data;
                    heaparr[i].data = temp;
                    ind++;
                }
            }
            k = k+1;
        }
        div = div*10;
    }

    printf("\n");
    free(heaparr);
    return 0;
}

it is giving me result

20 101 156 161 241 545 555 566 529 842 856 820 829 878 883 957 934 964

ans it should be.

20 101 156 161 241 529 545 555 566 820 829 842 856 878 883 934 964 957 

Answer 1

@gsamaras beat me to it, but here's a much smaller minimal example.

Start with:
  52, 93, 84, 54, 24

The entire pass in the 1s place leaves the values in the same places. Now look at the swap operations when processing the 10s place:

10s, k=0
10s, k=1
10s, k=2
  24, 93, 84, 54, 52 //The first swap mis-orders the "50s"
   ^---------------^
10s, k=3
10s, k=4
10s, k=5
  24, 54, 84, 93, 52
       ^-------^
  24, 54, 52, 93, 84 //Hence they stay out-of-order when they're moved up
           ^-------^
10s, k=6
10s, k=7
10s, k=8
  24, 54, 52, 84, 93
               ^---^
10s, k=9

Consider shifting the elements right to make space, rather than swapping, or do the processing of each decimal place out-of-place (i.e., alternating between two buffers).

Answer 2

Radix sort requires the the intermediate sorts to be stable, as you can read in Wikipedia. Here is a nice picture, explaining what stability is:

"An example of stable sort on playing cards. When the cards are sorted by rank with a stable sort, the two 5s must remain in the same order in the sorted output that they were originally in. When they are sorted with a non-stable sort, the 5s may end up in the opposite order in the sorted output."

---

So, in your code, when you are swapping two elements, you do not make sure that the stability is preserved for the element you take from the begining and are pushing back towards the end, which breaks the requirement of radix sort, thus producing undesired effects.

Inspired by GeeksforGeeks, I transformed your code to use Counting sort (which is stable for the intermediate sorting steps):

#include <stdio.h>
#include <stdlib.h>
#include <math.h>       /* pow */

struct heap {
    int data;
};

void print(struct heap* heaparr)
{
    for(int i = 0; i < 18; i++)
        printf("%d ", heaparr[i].data);
    printf("\n");

}

// A function to do counting sort of arr[] according to
// the digit represented by exp.
struct heap* countSort(struct heap* heaparr, int n, int exp)
{
    int output[n]; // output array
    int i, count[10] = {0};

    // Store count of occurrences in count[]
    for (i = 0; i < n; i++)
        count[ (heaparr[i].data/exp)%10 ]++;

    // Change count[i] so that count[i] now contains actual
    //  position of this digit in output[]
    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // Build the output array
    for (i = n - 1; i >= 0; i--)
    {
        output[count[ (heaparr[i].data/exp)%10 ] - 1] = heaparr[i].data;
        count[ (heaparr[i].data/exp)%10 ]--;
    }

    // Copy the output array to arr[], so that arr[] now
    // contains sorted numbers according to current digit
    for (i = 0; i < n; i++)
        heaparr[i].data = output[i];
    return heaparr;
}

int main()
{
    int arr[18] = {545, 934, 829, 883, 842, 957, 241, 856, 878, 101, 555, 20, 964, 529, 156, 161, 566, 820};
    int i;

    struct heap *heaparr = malloc(sizeof(struct heap) * 18);

    for(i=0; i<18; i++) {
        heaparr[i].data = arr[i];
    }

    int k = 0, div = 1;

    while(div<=100 ){
        k=0;
        while(k<10) {
            for(i=0; i<18; i++) {
                countSort(heaparr, 18, (int)pow(10, heaparr[i].data/div% 10));
            }
            k = k+1;
        }
        div = div*10;
    }
    print(heaparr);
    free(heaparr);
    return 0;
}

which gives:

20 101 156 161 241 529 545 555 566 820 829 842 856 878 883 934 957 964

However, this should be just an example to get you started.