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 (ie "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:
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.
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. Ie, 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.
If you use a bucket number that is a power of 2, you can do this using bit operations.
Example
16 = 2^4 buckets:
This allows you to calculate the digit using
int input = ...
int digitNumber = ... // digit number from last digit to first one
int bucket = (index >> (4*digitNumber)) & ((1 << 4) - 1); // (index >> (4*digitNumber)) & 0xF
You just need to take care when using the most significant bit, since swapping this bit swaps the sign of the number represented as well. This means you also need to do sort by sign.
This is just a optimisation for powers of 2. In general you can find the digits by using
bucket = (input / d) % b;
Where d = 1=b^0 , b = b^1 , b*b = b^2 , ... , b^n ( ^ = exponentiation not XOR here).
This does not work on negative numbers though... You also need to handle negative numbers differently with that formula.
You have clearly understood the gist of the algorithm. You are interested in just a small implementation detail.
In decimal system we have the following number representation:
n = 100*a0 + 101*a1 + 102*a2 + ... + 10i*ai + ... = ∑10i*ai
where 0 ≤ ai ≤ 9 is a digit.
Examples:
4 = 100 *4 + 101*0 + 102*0 + ...
104 = 100 *4 + 101 *0 + 102 *1 + ...
In fact you always have a digit in any place. Those leading zeros are just not written in decimal number representation.
So consider using this function to find a digit in place:
int dig(int num, int place) {
// divide by powerOf10 to put away lower place digits
// take the reminder of division by 10 - the lowest digit
return num / powersOf10[place] % 10;
}
Precalculate powersOf10 array before.
上一篇: 非常基本的基数排序
下一篇: 你如何处理每个整数基数排序的地方？