Radix Sort is the answer when elements are in the range from 1 to n^2. 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.
Radix Sort:
Radix Sort basically consists of the following steps:
- Take the Least Significant Digit of each element
- Sort the list of elements based on the digit, but keep the order of elements with the same digit i.e. sorting stably.
- Repeat the sort with each more significant digit.
Radix sort can be implemented in many ways like counting sort and bucket sort. Here, we’ll be using bucket sort technique. Bucket sort is mainly useful when input is uniformly distributed over a range.
RECOMMENDED: Characteristics or features of an Algorithm
Time Complexity:
T(n) = O(nd) ≈ O(n) , if d is small Here, n is input size d is number of digits in input integers.
Implementation of Radix Sort :
Following is a simple implementation of radix sort in Python.
For easier understanding, the value of radix, r is 10.
It is recommended to go through Bucket Sort for understanding why how bucket sorting works.
# Python program for implementation of Radix Sort using bucket sort technique def radixSort(a): # radix r = 10 maxlength = False temp, place = -1, 1 while not maxlength: maxlength = True # create buckets size 10 as integers are decimal numbers # so they can hold numbers from 0-9 only, that's why size of 10 buckets = [list() for _ in range(r)] for i in a: temp = int(i/place) # store elements in buckets # using least significant digit as bucket index buckets[temp % r].append(i) if maxlength and temp > 0: maxlength = False d = 0 for b in range(r): buck = buckets[b] # store back elements in array A # in the same order they're stored in buckets for i in buck: a[d] = i d += 1 place *= r # create array a = [18, 4, 823, 61, 234] #Function call radixSort(a) #function to print the sorted array for i in range(len(a)): print(a[i])
Output:
4 18 61 234 823
Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.