Javascript Algorithm – Radix Sort
A lower bound algorithm like Merge Sort, Heap Sort, Quick-Sort, etc can not do better than nLogn.
What if the elements are in the range from 1 to n2?
We can’t use counting sort because counting sort will take O(n2) which is worse than comparison-based sorting algorithms. Can we sort such an array in linear time?
Radix Sort is the answer.
Radix sort algorithm is a non-comparison based sorting algorithm, it can be grouped by number place and position. Radix sort works by making two passes over data set, in this case, the set of integers from 0 to 99. The first pass sort the numbers based on the 1s digit, and the second pass sort number based on the 10s digit. Each number is placed in a bin.
Before reading this article, please review Queue data structure and implementation.
Now, let’s take a step by step implementation.
We will sort below number via implementing Radix Sort
For implementing the Radix Sort algorithm we define some empty bins/arrays, which will have an allocation from 0 to 9. It looks like this.
Important!
Radix sort work with 10s digit dividation. What is it!!
It divides bin/number depends on the 10 digit.
1s digit = first number from the right and
so on…
In below image number 578 can be divide into 3 digit, 1s, 10s, 100s.
As similiar method can be applied to all number.
In number 32, 1s digit is 2 and 10s digit is 3.
In number 2, 1s digit is 2, and there is no 10s digit.
Now we have a basic understanding of Radix sort.
Lets go back to our use-case
Divide number into bin via 1s digit
Output
Now lets move back to 10s digit
Based on 1s and 10s our sorting should look like something below.
Show me the code
Testing
