Radix Sort
This is the algorithm used in old card punch
machines. "Sort by each digit, and put back in the hopper." Can
sort on most significant digit or least significant first. We
alphabetize via the most significant digit, but Radix Sort starts with the
leash significant digit.
| 329 |
|
720 |
|
720 |
|
329 |
| 457 |
|
355 |
|
329 |
|
355 |
| 657 |
|
436 |
|
436 |
|
436 |
| 839 |
Þ |
457 |
Þ |
839 |
Þ |
457 |
| 436 |
|
657 |
|
355 |
|
657 |
| 720 |
|
329 |
|
457 |
|
720 |
| 355 |
|
839 |
|
657 |
|
839 |
| input |
|
1st pass |
|
2nd pass |
|
3rd pass |
Radix-Sort ( A, d )
- for i 1 to d
- do use a stable sort to sort
array A on digit i
Why must it be stable? Each new pass must not "undo" what was
done on the previous passes. This is due to least significant digit first.
Is radix sort correct? With stability yes.
Running time: (d digits)
d times the running time of stable sort in the loop. Using digits
k = 10, so counting sort works with O (n), so radix runs in O
(n d). Note that if there are d-digits, then you can sort (one pass) of up
to bd numbers in O (n), and d = logb n, so at
best O ( n lg n )
|
