Radix Sort – Explanation, Pseudocode and Implementation
|Radix Sort is a non-comparative sorting algorithm with asymptotic complexity O(nd). It is one of the most efficient and fastest linear sorting algorithms. Radix sort was developed to sort large integers. As integer is treated as a string of digits so we can also call it as string sorting algorithm.
The lower bound for comparison based sorting algorithm is O(n*log n) like merge sort, quick sort, heap sort. So radix sort is efficient than comparison sorting algorithm until the number of digits (key) is less than log n. Counting sort can’t be used if a range of key value is large (suppose range is 1 to n^{2}) so radix sort is the best choice to sort in linear time.
In radix sort, we first sort the elements based on last digit (least significant digit). Then the result is again sorted by second digit, continue this process for all digits until we reach most significant digit. We use counting sort to sort elements of every digit, so time complexity is O(nd).
Here are some key points of radix sort algorithm –
- Radix Sort is a linear sorting algorithm.
- Time complexity of Radix Sort is O(nd), where n is the size of array and d is the number of digits in the largest number.
- It is not an in-place sorting algorithm as it requires extra additional space.
- Radix Sort is stable sort as relative order of elements with equal values is maintained.
- Radix sort can be slower than other sorting algorithms like merge sort and quick sort, if the operations are not efficient enough. These operations include inset and delete functions of the sub-list and the process of isolating the digits we want.
- Radix sort is less flexible than other sorts as it depends on the digits or letter. Radix sort needs to be rewritten if the type of data is changed.
Let’s understand it with an example –
Observe the image given below carefully and try to visualize the concept of this algorithm.
In the above example:
For 1^{st} pass: we sort the array on basis of least significant digit (1s place) using counting sort. Notice that 435 is below 835, because 435 occurred below 835 in the original list.
For 2^{nd} pass: we sort the array on basis of next digit (10s place) using counting sort. Notice that here 608 is below 704, because 608 occurred below 704 in the previous list, and similarly for (835, 435) and (751, 453).
For 3^{rd} pass: we sort the array on basis of most significant digit (100s place) using counting sort. Notice that here 435 is below 453, because 435 occurred below 453 in the previous list, and similarly for (608, 690) and (704, 751).
Pseudocode of Radix Sort
Radix-Sort(A, d) //It works same as counting sort for d number of passes. //Each key in A[1..n] is a d-digit integer. //(Digits are numbered 1 to d from right to left.) for j = 1 to d do //A[]-- Initial Array to Sort int count[10] = {0}; //Store the count of "keys" in count[] //key- it is number at digit place j 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] //Build the resulting array by checking //new position of A[i] from count[k] for i = n-1 downto 0 do result[ count[key of(A[i])] ] = A[j] count[key of(A[i])]-- //Now main array A[] contains sorted numbers //according to current digit place for i=0 to n do A[i] = result[i] end for(j) end func
Asymptotic Analysis of Radix Sort
In this algorithm running time depends on intermediate sorting algorithm which is counting sort. If the range of digits is from 1 to k, then counting sort time complexity is O(n+k). There are d passes i.e counting sort is called d time, so total time complexity is O(nd+nk) =O(nd). As k=O(n) and d is constant, so radix sort runs in linear time.
Worst Case Time complexity: O (nd)
Average Case Time complexity: O(nd)
Best Case Time complexity: O(nd)
Space Complexity: O(n+k)
Data Structure: Array
Sorting In Place: No
Stable: Yes
Implementation of Radix Sort in C and Java programming language
C
// C implementation of Radix Sort #include<stdio.h> #include<stdlib.h> // This function gives maximum value in array[] 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; } // Main Radix Sort sort function void radixSort(int A[], int n) { int i,digitPlace = 1; int result[n]; // resulting array // Find the largest number to know number of digits int largestNum = getMax(A, n); //we run loop until we reach the largest digit place while(largestNum/digitPlace >0){ int count[10] = {0}; //Store the count of "keys" or digits in count[] for (i = 0; i < n; i++) count[ (A[i]/digitPlace)%10 ]++; // Change count[i] so that count[i] now contains actual // position of this digit in result[] // Working similar to the counting sort algorithm for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the resulting array for (i = n - 1; i >= 0; i--) { result[count[ (A[i]/digitPlace)%10 ] - 1] = A[i]; count[ (A[i]/digitPlace)%10 ]--; } // Now main array A[] contains sorted // numbers according to current digit place for (i = 0; i < n; i++) A[i] = result[i]; // Move to next digit place digitPlace *= 10; } } // Function to print an array void printArray(int A[], int n) { int i; for (i = 0; i < n; i++) printf("%d ", A[i]); printf("\n"); } // Driver program to test above functions 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); radixSort(a, n); printf("Sorted Array: "); printArray(a, n); return 0; }
JAVA
/* Java implementation Radix Sort */ package codingeek; import java.util.Arrays; import java.util.Scanner; public class RadixSort { public static void main(String arg[]){ int a[] = {209,3,48,91,66,101,30,795}; //print unsorted array using Arrays.toString() System.out.print("Unsorted array: "); System.out.println(Arrays.toString(a)); RadixSort rs= new RadixSort(); rs.radixSort(a); System.out.print("Sorted array: "); //print sorted array System.out.println(Arrays.toString(a)); } // This function gives maximum value in array[] public int getMax(int A[]) { int max = A[0]; for (int i = 1; i < A.length; i++){ if (A[i] > max) max = A[i]; } return max; } // Main Radix Sort sort function public void radixSort(int A[]) { int digitPlace = 1; int n=A.length; int result[]=new int[n]; // resulting array // Find the largest number to know number of digits int largestNum = getMax(A); //we run loop until we reach the largest digit place while(largestNum/digitPlace >0){ int count[]=new int[10]; //Initializing counting array C[] to 0 for (int i=0; i <10; i++) count[i] = 0; //Store the count of "keys" or digits in count[] for (int i = 0; i < n; i++) count[ (A[i]/digitPlace)%10 ]++; // Change count[i] so that count[i] now contains actual // position of this digit in result[] // Working similar to the counting sort algorithm for (int i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the resulting array for (int i = n - 1; i >= 0; i--) { result[count[ (A[i]/digitPlace)%10 ] - 1] = A[i]; count[ (A[i]/digitPlace)%10 ]--; } // Now main array A[] contains sorted // numbers according to current digit place for (int i = 0; i < n; i++) A[i] = result[i]; // Move to next digit place digitPlace *= 10; } } }
Output:-
Unsorted array: 209,3,48,91,66,101,30,795
Sorted array: 3,30,48,66,91,101,209,795
Radix Sort is one of the most efficient and fastest linear sorting algorithms. It is simple to understand and easy to implement. Radix Sort is a good choice for many programs which need a fast sort.
Radix Sort can handle larger keys more efficiently as compare to Counting Sort. Radix sort is most equally efficient as the best comparison-based sorts (and worse if keys are much longer than log n).
Another linear sorting algorithm is bucket sort which we will discuss in the future post.
Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.
Do not forget to SHARE and SUBSCRIBE.
Keep Learning… Happy Learning..