Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

2019-03-28 Radix Sort

posted Mar 28, 2019, 6:03 AM by Konstantinovich Samuel   [ updated Mar 29, 2019, 6:44 AM ]
Goal: Sort numbers without comparing them

Respond to the prompts in your notes:
1. How can we sort an array of single digit numbers without comparing the values to eachother? 
        Hint: This can be done in linear time!
2. Would this work with double digit numbers?
3. When would this method no longer be viable? / Why?

The radix sort is a non-comparative sort! We never compare two values to eachother.

If we were to use a stable sort on each digit of the numbers in a list:

-Start with the least significant digit and sort by that
-Move to the next significant digit and sort by that (repeat until no more digits in any of the numbers)

Note: Since the sort is stable, we retain the order of the less significant digits each time.
-After each pass, look to the left of the current digit, and notice that if that were the entire number the list would be sorted.

Some simpler examples:
If we had  [5xx, 4xx, 2xx, 3xx, 7xx]
Since there are no duplicates in the most significant digit, the list would be ultimately sorted by the hundreds digits:
[2xx, 3xx, 4xx, 5xx, 7xx]

If we had duplicates they would use the order of the highest different value:
eg  [133, 123]
When sorting by the one's place would remain in the same order.
When sorting by the ten's place they would flip to   [123, 133]
When sorting by the hundreds place, they woudld remain in the same order. (the tens place determines the order)
end result : [123, 133]

Write at least part of the question, AND the answer to each in your notes.
4. [How many passes] do you need to make for this algorithm?
5. [What operations do you want to be fast] for this algorithm to work quickly?
6. [What is the runtime] of this algorithm?