Search code examples
javaalgorithmsortingradix-sort

How do you handle the places for each integer Radix Sort?

Background:
I am looking at radix sort, and I believe I have a pretty good idea of how the algorithm works in general. However, I am having trouble understanding how you actually "interpret" each of the elements as you go through the list.

I'll explain a bit more:

Lets say I have arrayToSort = [50, 4, 2, 10, 22, 284]

From my understanding, I'd go from 0 to 9 sorting by the tens place. So, I'd have:

Bucket 0: 50, 10
Bucket 1: empty
Bucket 2: 2, 22
Bucket 3: empty
Bucket 4: 4, 284 (And 5 - 9 are empty)

Then, I'd reconstruct the array by putting the elements from each bucket (starting with bucket 0) into the new array.

Problem:
Here is where I get stuck: For the hundredths place, I'd do the same thing I did for the first iteration. But what do I do for elements like 2 and 4? I am assuming I need to "pad" them with leading zeros. However, if I do that, does that mean I need to treat each element as a string while I'm doing the comparison in order to get that padding (i.e. "0002")? From my understanding, Java (the language I'm using) doesn't implement integers with leading zeros. But switching between strings and ints seems inefficient.

Question:
How are you supposed to handle the problem of some integers not having the same number of places as other integers in the array?

I have looked at pseudocode and implementations of the algorithm, and I am still confused about how they are dealing with getting the value of each place in the integer. I can't understand how you can implement the algorithm without leading zeros (and converting the integers to strings), and the examples I have seen don't do that. Here are a couple of sites I have tried:

  1. Oregon State Radix Sort
  2. Geek Viewpoint Radix Sort

Side note:
This isn't homework in case anybody wants to know. I'm just trying to become more familiar with different algorithms and how to implement them.

Solution

  • No worries. The math provides the "padding" you're thinking about.

    The first time through, the 1's place gives the bucket. In the Budd code you gave, that's the computation

    hashIndex = (data[i] / 1) % 10;

    This produces values from 0 to 9 that depend on the least significant digit. I.e., for 10, 101, 942, 13, 4l you'd get 0,1,2,3,4.

    In the second iteration, this becomes

    hashIndex = (data[i] / 10) % 10;

    The bucket indices will be the 10's digit: 1,0,4,1,0.

    Just for fun the third iteration, 

    hashIndex = (data[i] / 100) % 10;

    so you have: 0,1,9,0,0.

    In the next iteration, you'd of course get all zeroes.