Radix Sort

Radix sort is one of the sorting algorithms used to sort a list of integer numbers in order. In radix sort algorithm, a list of integer numbers will be sorted based on the digits of individual numbers. Sorting is performed from least significant digit to the most significant digit.

Radix sort algorithm requires the number of passes which are equal to the number of digits present in the largest number among the list of numbers. For example, if the largest number is a 3 digit number then that list is sorted with 3 passes.

Step by Step Process

The Radix sort algorithm is performed using the following steps..

Step 1 - Define 10 queues each representing a bucket for each digit from 0 to 9.

Step 2 - Consider the least significant digit of each number in the list which is to be sorted.

Step 3 - Insert each number into their respective queue based on the least significant digit.

Step 4 - Group all the numbers from queue 0 to queue 9 in the order they have inserted into their respective queues.

Step 5 - Repeat from step 3 based on the next least significant digit.

Step 6 - Repeat from step 2 until all the numbers are grouped based on the most significant digit.

Algorithm for Radix Sort

Algorithm for RadixSort (ARR, N)
Step 1: Find the largest number in ARR as LARGE
Step 2: [INITIALIZE] SET NOP = Number of digits in LARGE
Step 3: SET PASS =
Step 4: Repeat Step 5 while PASS <= NOP-1
Step 5:SET I = and INITIALIZE buckets
Step 6:Repeat Steps 7 to 9 while I<N-1
Step 7:SET DIGIT = digit at PASSth place in A[I]
Step 8:Add A[I] to the bucket numbered DIGIT
Step 9:INCEREMENT bucket count for bucket numbered DIGIT
 [END OF LOOP]
Step 1 :Collect the numbers in the bucket
 [END OF LOOP]
Step 11: END

Example

Sort the numbers given below using radix sort.

345, 654, 924, 123, 567, 472, 555, 808, 911

In the first pass, the numbers are sorted according to the digit at ones place. The buckets are pictured upside down as shown below.

After this pass, the numbers are collected bucket by bucket. The new list thus formed is used as an input for the next pass. In the second pass, the numbers are sorted according to the digit at the tens place. The buckets are pictured upside down.

In the third pass, the numbers are sorted according to the digit at the hundreds place. The buckets are pictured upside down.

The numbers are collected bucket by bucket. The new list thus formed is the final sorted result. After the third pass, the list can be given as

123, 345, 472, 555, 567, 654, 808, 911, 924.

Advantages:

Radix sort algorithm is well known for its fastest sorting algorithm for numbers and even for strings of letters.
Radix sort algorithm is the most efficient algorithm for elements which are arranged in descending order in an array.

Disadvantages:

Radix sort takes more space than other sorting algorithms.
Poor efficieny for most elements which are already arranged in ascending order in an array.
When Radix sort algorithm is applied on very small sets of data(numbers or strings), then algorithm runs in 0(n) asymptotic time.

Program

	#include <stdio.h>
 	int largest(int a[]);
 	void radix_sort(int a[]);
 	void main()
 	{
 		int i;
 		int a[10]={90,23,101,45,65,23,67,89,34,23};
 		radix_sort(a);
 		printf("\n The sorted array is: \n");
 		for(i=0;i<10;i++)
 		printf(" %d\t", a[i]);
 	}

 	int largest(int a[])
 	{
 		int larger=a[0], i;
 		for(i=1;i<10;i++)
 		{
 			if(a[i]>larger)
 			larger = a[i];
 		}
 		return larger;
 	}
 	void radix_sort(int a[])
 	{
 		int bucket[10][10], bucket_count[10];
 		int i, j, k, remainder, NOP=0, divisor=1, larger,pass;
 		larger = largest(a);
 		while(larger>0)
 		{
 			NOP++;
 			larger/=10;
 		}
 		for(pass=0;pass<NOP;pass++) // Initialize the buckets
 		{
 			for(i=0;i<10;i++)
 			bucket_count[i]=0;
 			for(i=0;i<10;i++)
 			{
 				// sort the numbers according to the digit at passth place
 				remainder = (a[i]/divisor)%10;
 				bucket[remainder][bucket_count[remainder]] = a[i];
 				bucket_count[remainder] += 1;
 			}
 // collect the numbers after PASS pass
 			i=0;
 			for(k=0;k<10;k++)
 			{
 				for(j=0;j<bucket_count[k];j++)
 				{
 					a[i] = bucket[k][j];
 					i++;
 				}
 			}
 			divisor *= 10;

		 }
		 }

Output:

The sorted array is:

101

Complexity of Radix Sort

To sort an unsorted list with 'n' number of elements, Radix sort algorithm needs the following complexities...

Worst Case : O(n)

Best Case : O(n)

Average Case : O(n)

Menu