Radix sort is a sorting algorithm that sorts the elements by first grouping the individual digits of the same place value. Then, sort the elements according to their increasing/decreasing order.
Radix Sort's time complexity is O(n * x), where n is the size of the array and 'x' is the number of digits in the largest number.
-
Finds the largest element in the array and calculates the number of digits in it. Number of digits in the largest element are calculated as it is required to go through all the significant places of all elements.
-
Goes through each significant place one by one.
-
Uses Counting Sort to sort the digits at each significant place.
-
Repeats "Step-3" until it sorts the elements based on the digits at last place.
Given array is
[ 121, 432, 564, 23, 1, 45, 788 ]
Sorted array is
[ 1, 23, 45, 121, 432, 564, 788 ]
FIRST PASS
- Sorts the elements based on the unit place digits.
After first pass array looks like..
[ 121, 1, 432, 23, 564, 45, 788 ]
SECOND PASS
- Sorts the elements based on digits at tens place.
After second pass array looks like..
[ 1, 121, 23, 432, 45, 564, 788 ]
THIRD PASS
- Finally, sorts the elements based on the digits at hundreds place.
After third pass array looks like..
[ 1, 23, 45, 121, 432, 564, 788 ]