Which sorting is below one?
1. suppose that we want to sort 10 integers in the range of 0-999.
then we have to use 1000bins. which would not be efficient.
2. So we use binsort function to sort 10 numbers based on least significant
digit. Which would potentially require only 10 bins. as last digit
can range from only 0-to-9.
3. again we use bin sort to sort the list we obtain from step 2, and sort
based on second least siginificant digit. again bin is 10 range.
nodes having same second digit, will remain sort by step 2.
4. then again use bin sort to sort the list we obtain from step 3, and sort
based on most siginificant digit.if there is no 3rd digit, it is 0.
5. finally we get completely sorted list, by collection all nodes from all bins
6. But here we are doing bin sort only thrices, each time with 30 steps,
10 to initialize, 10 to distribute, 10 to collect from bins.
so roughly it takes only 90 steps. but if we do the same using a single
bin sort, for initialization only it takes 1000 steps, which is heavy.
7. So this sorting is efficient compared to normal bin sort.
Efficient Bin Sort
Bucket bin sort.
This is called as Radix sort, as the no of bins range is limited to number base value. here in this example since we are using decimal numbers max bins used are only of 10 radix. so this is Radix sort.
Back To Top