Radix sort algorithm explanation with example

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.

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

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

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 

---

[wpusb]