26-06-2012, 02:48 PM
Radix Sort
7.08.RadixSort.ppt (Size: 954.5 KB / Downloads: 32)
Suppose we want to sort 10 digit numbers where repetitions may occur
We could use bucket sort, but this would require the use of 1010 buckets
Using only one byte per counter, this would require 9 GiB
Very sub-optimal if we were sorting only, say 10 000 numbers
Run-time Analysis
Bucket sort is Q(n + m) where m is the number of buckets
Restricting ourselves to either decimal digits or bits ensures that m = Q(1)
How often must we iterate to sort numbers on the range 0, …, N – 1?
We require ⌊log10(N)⌋ + 1 digits or ⌊log2(N)⌋ + 1 bits
This is why Arabic numbers are so powerful
Run time is therefore Q(n ln(N))
For this to be faster than previous sorting algorithms, it must be true that ln(N) < ln(n) or N << n
Therefore, it is only truly useful if we are sorting lists of relatively small numbers with very significant amount of duplications
Summary
Radix sort uses bucket sort on each digit of a set of numbers to be sorted:
Interesting in theory, less useful in practice
Useful only if sorting numbers with significant duplication
The idea is used elsewhere