As with the previous post, I’ll keep talking about sorting algorithms (NOT based on comparison) that have a linear complexity. This post, in fact, is about Radix Sort.
How Radix Sort works
As I said in the previous post in order to achieve a linear complexity we need more restrictive hypotheses. In this case, the hypothesis is:
- The elements to order are represented on d digits.
I gotta tell the truth: Radix Sort is not so smart. Everything it does is order the array from the least significant digit to the (d-1)-nth digit.
It is not smart because we need to use another algorithm to order the digits and this algorithm must be stable.
Python Implementation
For this specific implementation, I chose to use a specific version of Counting Sort (the algorithm I described to you in the previous post). Here is the Python implementation:
As you can notice 85% of the code is related to the implementation of a version of Counting Sort that is able to sort based on the digit.
I developed this code for a university exam and I realize now that it is pretty ugly. For this reason, I challenge you to make a better version (it shouldn’t be so hard) and show me the result.
Conclusions
In this conclusion, I re-post some of the considerations I found on the slides of my University teacher. Why would someone choose Radix Sort over Quicksort? There are some drawbacks to both of them. Radix Sort usually takes fewer steps than Quicksort, but every step requires more time. On the other hand, when we use Counting Sort as a sub-sorting algorithm there is high memory consumption. For now, that’s all! See you with the next post about Sorting Algorithms.
As usual, if you want to see the source code you can check my GitHub!
