#### Sorting Algorithms Algorithms radix sort counting sort

Reading time: 25 minutes | Coding time: 10 minutes

Radix Sort is an efficient non-comparison based sorting algorithm which can sort a dataset in linear O(N) time complexity and hence, can be better than other competitive algorithm like Quick Sort. It uses another algorithm namely Counting Sort as a subroutine.

• Number of digits in an Integer is determined by:
• its base
• very less compared to the data

Numbers increase linearly but number of digits increase logarithmically.

Radix sort was developed to sort large integers. It considers integer as a string of digits so we can use Radix Sort to sort strings as well.

### Algorithm

• Do following for each digit i where i varies from least significant digit to the most significant digit.
• Sort input array using counting sort (or any stable sort) according to the i’th digit.

### Example

Assume the input array is:

[326, 453, 608, 835, 751, 435, 704, 690]

Based on the algorithm, we will sort the input array according to the one's digit (least significant digit).

The original array is sorted based on [6, 3, 8, 5, 1, 5, 4, 0] using Counting Sort

So, the array becomes [690, 751, 453, 704, 835, 435, 326, 608]

Now, we'll sort according to the ten's digit:

The above partially sorted array is sorted based on [9, 5, 5, 0, 3, 3, 2, 0] using Counting Sort

Now, the array becomes : [704, 608, 326, 835, 435, 751, 453, 690]

Finally , we sort according to the hundred's digit (most significant digit):

The above partially sorted array is sorted based on [7, 6, 3, 8, 4, 7, 4, 6] using Counting Sort

The array becomes : [326, 435, 453, 608, 690, 704, 751, 835] which is sorted.

Follow this image to understand the concept:

#### Why does sorting one digit place at a time work in Radix Sort?

Maintains the order of input data
It is in-place sorting
Uses counting sort
It is non comparison based
As Radix Sort maintains the order of the input data, the sorting of previous digits are maintained and adjusted only if the higher significant digit needs to be sorted.

### Pseudocode


for j = 1 to d do
int count[10] = {0};
for i = 0 to n do
count[key of(A[i]) in pass j]++
for k = 1 to 10 do
count[k] = count[k] + count[k-1]
for i = n-1 downto 0 do
result[ count[key of(A[i])] ] = A[j]
count[key of(A[i])]--
for i=0 to n do
A[i] = result[i]
end for(j)
end func


## Complexity Analysis

Best case time complexity:Ω(nk)

Average case time complexity:Θ(nk)

Worst case time complexity:O(nk)

Space complexity:O(n+k)

where n is the number of input data and k is the maximum element in the input data

Let there be d digits in input integers. Radix Sort takes O(d(n+b))* time where b is the base for representing numbers, for example, for decimal system, b is 10. What is the value of d? If k is the maximum possible value, then d would be O(logb(k)). So overall time complexity is O((n+b) * logb(k)). Which looks more than the time complexity of comparison based sorting algorithms for a large k.

Let us first limit k. Let k <= nc where c is a constant. In that case, the complexity becomes O(nLogb(n)). But it still doesn’t beat comparison based sorting algorithms.

What if we make value of b larger?. What should be the value of b to make the time complexity linear? If we set b as n, we get the time complexity as O(n). In other words, we can sort an array of integers with range from 1 to nc if the numbers are represented in base n (or every digit takes log2(n) bits).

• C
• Java

## C


#include<stdio.h>
#include<stdlib.h>
int getMax(int A[], int n)
{   int i;
int max = A[0];
for (i = 1; i < n; i++){
if (A[i] > max)
max = A[i];
}
return max;
}
{   int i,digitPlace = 1;
int result[n];
int largestNum = getMax(A, n);
while(largestNum/digitPlace >0){
int count[10] = {0};
for (i = 0; i < n; i++)
count[ (A[i]/digitPlace)%10 ]++;
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
for (i = n - 1; i >= 0; i--)
{   result[count[ (A[i]/digitPlace)%10 ] - 1] = A[i];
count[ (A[i]/digitPlace)%10 ]--;
}
for (i = 0; i < n; i++)
A[i] = result[i];
digitPlace *= 10;
}
}
void printArray(int A[], int n)
{   int i;
for (i = 0; i < n; i++)
printf("%d ", A[i]);
printf("\n");
}
int main()
{   int a[] = {209,3,48,91,66,101,30,795};
int n = sizeof(a)/sizeof(a[0]);
printf("Unsorted Array: ");
printArray(a, n);
printf("Sorted Array: ");
printArray(a, n);
return 0;
}


## Java


import java.io.*;
import java.util.*;
static int getMax(int arr[], int n){
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
static void countSort(int arr[], int n, int exp)
{
int output[] = new int[n];
int i;
int count[] = new int[10];
Arrays.fill(count,0);
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%10 ]++;
// Change count[i] so that count[i] now contains
// actual position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (i = n - 1; i >= 0; i--){
output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
count[ (arr[i]/exp)%10 ]--;
}
for (i = 0; i < n; i++)
arr[i] = output[i];
}
static void radixsort(int arr[], int n)
{ // Find the maximum number to know number of digits
int m = getMax(arr, n);
for (int exp = 1; m/exp > 0; exp *= 10)
countSort(arr, n, exp);
}
static void print(int arr[], int n)
{
for (int i=0; i<n; i++)
System.out.print(arr[i]+" ");
}
public static void main (String[] args)
{    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = arr.length;
print(arr, n);
}
}


• Fast when the keys are short i.e. when the range of the array elements is less.
• Used in suffix array constuction algorithms like Manber's algorithm and DC3 algorithm.
• Radix Sort is stable sort as relative order of elements with equal values is maintained.