RADIX SORT
Radix sort is the linear sorting algorithm that is used for integers. In Radix sort, there is digit
by digit sorting is performed that is started from the least significant digit to the most
significant digit.
The process of radix sort works similar to the sorting of student’s names, according to the
alphabetical order. In this case, there are 26 radices formed due to the 26 alphabets in
English. In the first pass, the names of students are grouped according to the ascending order
of the first letter of their names. After that, in the second pass, their names are grouped
according to the ascending order of the second letter of their name. And the process continues
until we find the sorted list.
Radix sort algorithm is a non-comparative sorting algorithm in computer science. It avoids
comparison by creating and categorizing elements based on their radix.
Radix Sort's time complexity of O(nd), where n is the size of the array and d is the number of
digits in the largest number.
The key idea behind Radix Sort is to exploit the concept of place value. It assumes that
sorting numbers digit by digit will eventually result in a fully sorted list. Radix Sort can be
performed using different variations, such as Least Significant Digit (LSD) Radix Sort or
Most Significant Digit (MSD) Radix Sort.
Radix sort is a stable sorting method that uses counting sort as a subroutine. It is
recommended to use radix sort on positive numbers only, however with some modification to
standard radix sort algorithm we can also sort an array containing negative elements.
Steps Involved in Radix sort to sort an array in ascending order are --
Find the maximum element of the array, let it be max
Find the number of digits in max, let it be k.
For eachi, ranging from 1 to k, apply the counting sort algorithm for theith least-
significant digit of each element. If any element has less than i digits consider 0 at its
place (Because 2929 can also be represented as 029029).
Radix Sort Algorithm
radixSort(array)
d <- maximum number of digits in the largest element
create d buckets of size 0-9
for i <- 0 to d
sort the elements according to ith place digits using countingSort
countingSort(array, d)
max <- find largest element among dth place elements
Notes compiled by:
Sangita Vishwakarma
DPGITM
initialize count array with all zeros
for j <- 0 to size
find the total count of each unique digit in dth place of elements and
store the count at jth index in count array
for i <- 1 to max
find the cumulative sum and store it in count array itself
for j <- size down to 1
restore the elements to array
decrease count of each element restored by 1
Time Complexity
o Best Case Complexity - It occurs when there is no sorting required, i.e. the array is
already sorted. The best-case time complexity of Radix sort is Ω(n+k).
o Average Case Complexity - It occurs when the array elements are in jumbled order
that is not properly ascending and not properly descending. The average case time
complexity of Radix sort is θ(nk).
o Worst Case Complexity - It occurs when the array elements are required to be sorted
in reverse order. That means suppose you have to sort the array elements in ascending
order, but its elements are in descending order. The worst-case time complexity of
Radix sort is O(nk).
Example of Radix Sort Algorithm
Let's assume we have an array =[682,244,73,6,535,123]
Here the maximum element is 682 which is of 3 digits, so we will apply the counting sort on
the least significant digit, i.e. last digit –
Notes compiled by:
Sangita Vishwakarma
DPGITM
Now we apply counting sort on the second digit of the numbers, after which the numbers will
get sorted on the basis of 2nd least-significant digits –
Now it's time to sort the numbers based on the3rd digit from right, .i.e. the Most-significant
digits. –
And it's done, now the array is sorted in ascending order.
Notes compiled by:
Sangita Vishwakarma
DPGITM
