Radix Sort


Radix Sort

Prerequisite: Counting Sort

QuickSort, MergeSort, HeapSort are comparison based sorting algorithms.
CountSort is not comparison based algorithm. It has the complexity of O(n+k), where k is the maximum element of the input array.
So, if k is O(n) ,CountSort becomes linear sorting, which is better than comparison based sorting algorithms that have O(nlogn) time complexity.
The idea is to extend the CountSort algorithm to get a better time complexity when k goes O(n2).
Here comes the idea of Radix Sort.

Algorithm:

For each digit i where i varies from the least significant digit to the most significant digit of a number
Sort input array using countsort algorithm according to ith digit.
We used count sort because it is a stable 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. This is how our algorithm works.

An implementation in C:

void countsort(int arr[],int n,int place){ int i,freq[range]={0}; // range for integers is 10 as digits range from 0-9 int output[n]; for(i=0;i<n;i++) freq[(arr[i]/place)%range]++; for(i=1;i<range;i++) freq[i]+=freq[i-1]; for(i=n-1;i>=0;i--){ output[freq[(arr[i]/place)%range]-1]=arr[i]; freq[(arr[i]/place)%range]--; } for(i=0;i<n;i++) arr[i]=output[i]; } void radixsort(ll arr[],int n,int maxx){ // maxx is the maximum element in the array int mul=1; while(maxx){ countsort(arr,n,mul); mul*=10; maxx/=10; } }

An implementation in Python:

def counting_sort(arr, max_value, get_index): counts = [0] * max_value # Counting - O(n) for a in arr:s counts[get_index(a)] += 1 # Accumulating - O(k) for i, c in enumerate(counts): if i == 0: continue else: counts[i] += counts[i-1] # Calculating start index - O(k) for i, c in enumerate(counts[:-1]): if i == 0: counts[i] = 0 counts[i+1] = c ret = [None] * len(arr) # Sorting - O(n) for a in arr: index = counts[get_index(a)] ret[index] = a counts[get_index(a)] += 1 return ret

More Information

This article needs improvement. You can help improve this article. You can also write similar articles and help the community.