I am stuck at implementing Radix sort recursively

Question

I'm required to implement a programm that sorts numbers ranging from 0 to 99999 recursively (this is basically Radix sort). The process itself is kinda simpel: The user types in an array that contains those numbers in the main method. Then, the main method calls for the sort-method where I create a two-dimensional array named 'space' with 10 rows and 1 column. Then, I divide every number in the array by the digit, which would be 10.000 in the first run. So, for example, 23456 / 10000 = 2,3456 = 2 (in java), hence, the programm puts this number in space[2][0], so in the second row. Then, we take this entire row and extend it, which is done in the putInBucket-method. We do this in order to make sure that we can put another number into the same row.

We do this for every number that is inside the 'numbers'-array. Then, we want to work with these rows and sort them again by the same principle, but now we take a look at the second digit. We want to do this from left to right, not from right to left. So, if our second row would look like this

[23456, 24567],

we'd want to compare the 3 and the 4, which leads to 23456 < 24567.

We do this with the help of the recursive call at the end of the sort method. Now, this is where I am lost. I simply don't know how to manipulate the digit-variable in order to be able to work with the second, third, ... digit of each number. In the first run, as you see, this can be simply done by dividing through 10.000, but I didn't find a way to go further from here.

Please note: Yes, this is a homework question, hence, I'm only allowed to use primitives here. We didn't go through stuff like math.pow(...) yet. Thanks in advance!

public static int[] sort(int[] numbers, int digit) {

  if (numbers.length == 0)
    return numbers;

  int[][]space = new int[10][1];
  int i, j = 0;

  for (j = 0; j < numbers.length; j++) {
    i = numbers[j] / digit;
    space[i][0] = numbers[j];
    space[i] = putInBucket(space[i], numbers[j]);
  }

  for (i = 0; i < space[i].length; i++) {
    sort(space[i], digit); //not sure how to work with digit here
  }

  return ... //not sure what to return here

}

private static int[] putInBucket(int[] bucket, int number) {

  int[] bucket_new = new int[bucket.length+1];

  for (int i = 1; i < bucket_new.length; i++) {
    bucket_new[i] = bucket[i-1];
  }

  return bucket_new;

}

public static void main (String [] argv) {

  int[] numbers = IO.readInts("Numbers: ");
  int digit = 10000;
  int[] bucket = sort(numbers, digit); 

}

Answer 1

To extract the last digit, the remainder operator % is your friend:

123 % 10 == 3

if you haven't covered the % operator yet, you can use

123 % 10 == 123 - (123 / 10 * 10) == 3

To extract another digit, you can first move it to the end with /:

123 / 10 == 12
12 % 10 == 2

You can therefore extract an arbitrary digit using

(number / mask) % 10 

where mask ∈ {..., 10000, 1000, 100, 10, 1}.

Extra credit

Radix sort is usually implemented in the binary number system instead because a binary digit (or a sequence thereof) can be extracted without performing a division, which is more efficient:

x % 16 == x & 15;
x \ 16 == x >> 4;

Also, if you are implementing this for real, you'd need a more efficient way to grow buckets (your implementation takes O(n) to add a single element to the bucket, adding n elements to the bucket therefore takes O(n^2), which makes your radix sort slower than insertion sort). Dynamic arrays are usually implemented with a more efficient geometric expansion.

Answer 2

This should work:

public static int[] sort(int[] numbers, int digit) {

     if (numbers.length == 0 || digit <= 0)
           return numbers;

     int[][]space = new int[10][10];
     int[] len = new int[10];
     int i, j = 0;

      for (j = 0; j < numbers.length; j++) {
            i = (numbers[j] / digit) % 10;
            len[i]++;
            for (int k = len[i] - 1; k > 0; k--) {
                space[i][k] = space[i][k - 1];
            }
            space[i][0] = numbers[j];
      }


      for (i = 0; i < 10; i++) {
          int[] bucket = new int[len[i]];
          for (int k = 0; k < len[i]; k++) 
              bucket[k] = space[i][k];
          space[i] = sort(bucket, digit / 10); 
      }

      int k = 0;

      for (i = 0; i < 10; i++) {
          for (j = 0; j < len[i]; j++) {
              numbers[k] = space[i][j];
              k++;
          }
      }

      return numbers; 

}

a) Firstly, space is allocated as having only one column. So, space[i] = bucket will not work.

Instead, you could declare it as int[10][10]. (Note: it will only support max of 10 values in one bucket). Or you may allocate new arrays programmatically. Or of course, a List might be better suited.

b) i = (numbers[j] / digit) % 10;

To get the required digit only. For eg: if the number is 12130, and digit = 1000, we want to set i to 2, not 12.

c) putInBucket replaced with an in-place loop.

d) For each bucket of space, we sort it by one digit lower by calling sort recursively.

e) Finally, the result to be returned (numbers), can be created by looping through space from digit 0 to 9.

Note: This solution could probably be made better.