Radix Sort: Algorithm, Program, Explanation and Examples

by

Radix sort is a non-comparative sorting algorithm that sorts elements digit by digit starting from least significant digit to most significant digit.

Suppose if you want to sort 10 elements in ascending order using radix sort, first sort the digit of unit place. After that sort the tenth place digit. This process will go till the most significant digits.

Let’s see an example to understand it clearly

Suppose we have 7 elements in an array.

{101, 45,543,233,321, 833,432}

After sorting unit digit our array will look like

{101, 321,432, 543, 233, 833, 45}

Radix sort uses counting sort as an intermediate sort.

How does radix sort work?

  • First Find the largest element in the array. In our case array is {101, 45, 543, 233, 212, 654, 833} and the maximum number in the array is 833 which has 3 digits.
  • We find maximum because we have to go up to the most significant digit which is calculated by a total number of digits of the maximum number. The maximum number is 833 and the total number of the digit in 833 is ‘3’. so the loop will go up to a hundred places.
  • Visit each significant place one by one from least significant digits to most significant digits. Here we sort elements of each signification digits using counting sort which is non-comparison sorting.

Let’s see a step-wise procedure how to sort elements using radix sort.

List which we have to sort using radix sort

With the help of algorithm we will sort the unit digit of the input array i.e. least significant digit

So after first pass array will become

After first pass of radix sort

Now we will sort the tenth digit place of the input array

So after the second pass array will look like

Now we will sort the 100th digit place of the input array i.e. most significant place

After the third pass array will be sorted

Sorted array using radix sort

Radix Sort Algorithm

Step 1: Find the maximum number in ARR as Max
Step 2: Calculate the Number of digits in Max and SET NOS = number of digit
Step 3: Repeat Step 4 to 8 for PASS = 1; PASS <= NOS
Step 4: Repeat Step 5 to 7for I=0 to I < Size of ARR
Step 5: SET DIGIT = Arr[I]
Step 6: Insert element Arr[I] to the bucket at index DIGIT
Step 7: Do Increment in bucket count for index DIGIT
[END OF FOR Loop]
Step 8: Pick elements from the bucket starting from index 0 and put in ARR
[END OF For LOOP]
Step 9: END

Radix Sort Complexity

Radix sort time complexity

Best-case performance: O(n)
Average Performance: O(n)

Worst-case performance: O(n)

Radix sort space complexity

Space complexity: O(n+k)

Radix Sort Program in C

#include <stdio.h>
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];
    return max;
}

void countSort(int arr[], int n, int exp) {
    int output[n];
    int i, count[10] = {0};
    for (i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;
    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];
    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];
}

void radixSort(int arr[], int n) {
    int m = getMax(arr, n);
    for (int exp = 1; m / exp > 0; exp *= 10)
        countSort(arr, n, exp);
}

int main() {
    int arr[100],i,n;
    printf("Enter the number of elements you want to sort:\n");
    scanf("%d",&n);
    printf("Now enter the %d elements you want to sort: \n",n);
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    printf("before sorting:\n");
    for(i=0;i<n;i++){
        printf("%d \t",arr[i]);
    }
    radixSort(arr, n);
    printf("\nSorted array: \n");
    for (int i = 0; i < n; i++)
        printf("%d \t", arr[i]);
    printf("\n"); 
    return 0;
}

Output : 

Enter the number of elements you want to sort:
5
Now enter the 5 elements you want to sort: 
23
11
43
56
12
before sorting:
23      11      43      56      12 
Sorted array: 
11      12      23      43      56

Real time Application of Radix sort

Radix Sort, known for its efficiency with large sets of data, finds practical applications in areas where the sorting of numerically represented data is crucial. A notable real-time application of Radix Sort is in the sorting of large databases, such as customer records, where each record is assigned a unique numerical identifier or key.

Database Sorting

In database management, especially those handling extensive sets of numeric IDs, Radix Sort can efficiently organize records by sorting them based on these identifiers. This sorting facilitates faster retrieval, search, and organization of data, essential for maintaining high-performance databases.

Sorting Phone Numbers

Telecommunication companies often deal with vast databases of phone numbers. Radix Sort can quickly sort these numbers, helping in efficient management, quick search, and retrieval operations, and ensuring customer data is organized systematically.

Sorting Dates

Applications that involve sorting dates, such as scheduling software, event management systems, and archival records, benefit from Radix Sort. By treating dates as numeric values (e.g., YYYYMMDD), Radix Sort can efficiently organize them in chronological order.

IP Address Sorting

In network management, sorting IP addresses is crucial for various tasks, including routing, allocation, and security. Radix Sort, with its ability to handle numbers efficiently, can sort IP addresses faster than comparison-based algorithms, improving network management operations.