Explanation of Radixsort

Question

Hi I am trying to understand the logic of Radix sort, I am referring to the code of wikipedia. Here is sort function of the sort which receives the array, and the number of elements. While the code is running perfectly fine , I am not able to understand the logic of the code. Inside while loop first we initialize a 10 digit bucket array, which holds the count of no of 1's,and 2's for first and second index of the array. But after that it is very difficult to understand what it is trying to do.

static void sort(int a[],int n)
{
int i=0;
int m =a[0];
int b[]=new int[n];
int exp=1;


      for (i = 0; i < n; i++)
      {
        if (a[i] > m)
          m = a[i]; 
      }

      while (m / exp > 0)
      {
        int bucket[] =new int[10];
        for (i = 0; i < n; i++)
          bucket[a[i] / exp % 10]++;


        for (i = 1; i < 10; i++)
          bucket[i] += bucket[i - 1];
        for (i = n - 1; i >= 0; i--)
          b[--bucket[a[i] / exp % 10]] = a[i];
        for (i = 0; i < n; i++)
          a[i] = b[i];
        exp *= 10;

          System.out.println("\nPASS   : ");
          for(int c:a){
        System.out.print(c+",");
    }
          System.out.println();
      }

}

Can anyone help me with this? Thanks

Answer 1

This code takes some effort to understand even if you know how radix sort works. It's easier to first understand the abstract description of radix sort than try to reverse-engineer it from this code.

Some technical observations about the code:

• The external loop controls exp which goes from 1,10,100... through consecutive powers of ten and determines which decimal digit of the numbers we currently sort on.
• The actual sorting into buckets is two-pass. The first inner loop computes counts for each bucket, the third spreads the numbers into respective buckets (going from n to 1 both in a[] and within each bucket.)
• The buckets are represented as intervals in the auxilliary b[] array (whose offsets are precomputed in the second inner loop based on the bucket counts from the first inner loop)
• After the second loop bucket[d] is the index of the upper end (exclusive) of the interval that will store the numbers whose active digit (the one we sort on) is d. The bucket intervals are filled from this end downwards.