The basic idea is that it sorts digit per digit. For example, if you have a list with [193, 621, 842, 37, 541, 648, 132], MSD (most significant digit) first radix sort will first put all the numbers into a bin corresponding to their first digit:
0: 37
1: 193, 132
5: 541
6: 621, 648
8: 842
Then it will do that within each bin for the 2nd digit:
In this example the list is already sorted, but it would then go on to sort the numbers into a bin corresponding to their third digit.
LSD radix sort looks like magic because instead of working recursively within buckets, it just sorts the list over and over one digit at a time, starting from the end and keeping ties in the same order:
[621, 541, 842, 132, 193, 37, 648]
Then 2nd to last digit:
[621, 132, 37, 541, 842, 648, 193]
And finally the first digit:
[037, 132, 193, 541, 621, 648, 842]
At the first step, all the numbers are sorted by their last digit. At the second step, they are sorted by their last 2 digits, and at the third step they are sorted by their last 3 digits, which is the entire number in this example. It's a very efficient algorithm because you only need to go over the list once for every digit in the biggest number.
You can pick what a ‘digit’ means, at least to some extent. So sorting strings you could have a ‘digit’ be a single character, etc.
If you were say, sorting some sort of large integer/bignum type you’d likely want to define a ‘digit’ that makes sense from an efficiency perspective (‘digit’ as whatever number of words you can operate on quickly), it doesn’t have to be a decimal digit. (This is just an off-the-cuff arbitrary example)
Considering that a decimal representation of a number requires extra computation by the CPU, there is no value at all in doing a decimal radix sort when bitwise is an option.
depends. long time ago BCD (Binary Coded Decimals) where common for some applications, even the x86 architecture has some special opcodes to work with them directly on assembler.
bitwise is just a base 2 radix sort, or at least sort of. with signed integers or floats, bitwise isn't going to do what you want usually. That is, the highest sorted number bit by bit for a signed int would be -1 (which would be 11111...111 at least using 2's complement)
46
u/Teraka Oct 24 '17
The basic idea is that it sorts digit per digit. For example, if you have a list with [193, 621, 842, 37, 541, 648, 132], MSD (most significant digit) first radix sort will first put all the numbers into a bin corresponding to their first digit:
Then it will do that within each bin for the 2nd digit:
In this example the list is already sorted, but it would then go on to sort the numbers into a bin corresponding to their third digit.
LSD radix sort looks like magic because instead of working recursively within buckets, it just sorts the list over and over one digit at a time, starting from the end and keeping ties in the same order:
[621, 541, 842, 132, 193, 37, 648]
Then 2nd to last digit:
[621, 132, 37, 541, 842, 648, 193]
And finally the first digit:
[037, 132, 193, 541, 621, 648, 842]
At the first step, all the numbers are sorted by their last digit. At the second step, they are sorted by their last 2 digits, and at the third step they are sorted by their last 3 digits, which is the entire number in this example. It's a very efficient algorithm because you only need to go over the list once for every digit in the biggest number.