Counting sort is a linear time sorting algorithm that sort in O(n+k) time when elements are in the range from 1 to k.
We can’t use counting sort because counting sort will take O(n2) which is worse than comparison-based sorting algorithms.
The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit.
Radix sort uses counting sort as a subroutine to sort.
Example:
Assume the input array is:
10,21,17,34,44,11,654,123
Based on the algorithm, we will sort the input array according to the one's digit (least significant digit).
0: 10
1: 21 11
2:
3: 123
4: 34 44 654
5:
6:
7: 17
8:
9:
So, the array becomes 10,21,11,123,24,44,654,17
Now, we'll sort according to the ten's digit:
0:
1: 10 11 17
2: 21 123
3: 34
4: 44
5: 654
6:
7:
8:
9:
Now, the array becomes : 10,11,17,21,123,34,44,654
Finally , we sort according to the hundred's digit (most significant digit):
0: 010 011 017 021 034 044
1: 123
2:
3:
4:
5:
6: 654
7:
8:
9:
The array becomes : 10,11,17,21,34,44,123,654 which is sorted.
0 Comments