Sorting algorithm 9: Radix Sort

In this chapter we shall learn about below topics:

Radix sort algorithm is an interesting sorting algorithm. Because this sort is not based on comparison, rather than it is based on buckets.

Radix Sort is a linear sort algorithm. The number of passes depends upon the number of digits in the maximum number in the array.

Step 1: We know that there are 10 digits from 0 to 9.

Hence we shall take 10 buckets labelled from 0 to 9 to store the sorted numbers.

Step 2: Then we shall take the max number in the given list. Then we shall start the algorithm by taking the right most digit and start placing them in the suitable numbered bucket.

Step 3: Once we have placed all the elements in the particular buckets, we shall take them out and place them in sorted order according to their Least significant digit and thus the first pass is completed.

Step 4: Then we shall repeat the the step 2 and 3 till all the passes are completed.

Our Unsorted array: {10, 15, 1, 60, 5, 100, 25, 50}

Here, 100 is the highest element, and has 3 digits. Algorithm takes maximum of 3 passes.

As the highest element has 3 digits, hence we make all the elements in the array to have 3 digits. Resulting array is as shown below:

{010, 015, 001, 060, 005, 100, 025, 050}
First we take the digits from one's place and place it in the according bucket.

0: 010, 060, 100, 050
1: 001, 
2:
3:
4:
5: 015, 005, 025
6:
7:
8:
9:
Sorted array:
{010, 060, 100, 050, 001, 015, 005, 025}

We take the 10's place and place it in the according bucket:
{010, 060, 100, 050, 001, 015, 005, 025}

0:100, 001, 005
1: 010, 015, 
2: 025
3:
4:
5: 050, 
6:060, 
7:
8:
9:
Sorted array: {100, 001, 005, 010, 015, 025, 050, 060}

Finally, we take the 100'th place of all the digits.
{100, 001, 005, 010, 015, 025, 050, 060}

0:001, 005, 010, 015, 025, 050, 060
1: 100
2:
3:
4:
5: 
6:
7:
8:
9:
Final sorted array: {001, 005, 010, 015, 025, 050, 060}

#include<stdio.h>


int get_max_element(int arr[], int length)
{
	int itr;
    int max_element = arr[0];
    for (itr = 1; itr < length; itr++){
        if (arr[itr] > max_element)
            max_element = arr[itr];
    }
    return max_element;
}


void RadixSort(int arr[], int length)
{
	int max_element = get_max_element(arr, length);
	int result_array[100] = {0}; // To store intermediate sorted array
	int itr = 0;// iterator
	int digit_place = 1; // initially it will be in 1's later goes to 10's and 100's etc

	while ( (max_element/digit_place) > 0 )
	{
		int digits_bucket [10] = {0}; // we have 10 digits, hence take 10 buckets

		for (itr = 0; itr < length; itr++)
		{
			// get the digit in the digit_place and increment the counter in digits_bucket
			digits_bucket[ (arr[itr] / digit_place ) % 10 ]++; 
		}

		for (itr = 1; itr < 10; itr++)
		{
			// counting the actual count
			digits_bucket[itr] += digits_bucket[itr - 1];
		}		

		for(itr = length - 1; itr >= 0 ; itr --)
		{
			result_array[ digits_bucket[ (arr[itr]/digit_place) % 10 ] - 1] = arr[itr];
			digits_bucket[(arr[itr]/digit_place) % 10 ] --;
		}

		//copy output form temp array to original array
		for (itr = 0; itr < length; itr++)
		{
			arr[itr] = result_array[itr];
		}		

		digit_place *= 10;

	}

}

void print_array(int array[], int length)
{
	int index = 0;

	printf("The sorted array is: \n");

	for(index = 0 ; index < length ; index++)
	{
		printf("%d\n",array[index] );
	}
}


int main(int argc, char const *argv[])
{
	
	int length = 0;
	int array[100];
	int index = 0;

	printf("Enter the length of the array\n");
	scanf("%d", &length);

	printf("Enter the array elements of length %d = \n", length);

	for (index = 0; index < length; ++index)
	{
		scanf("%d", &array[index]);
	}

	RadixSort(array, length);

	print_array(array, length);

	return 0;
}

Enter the length of the array
4
Enter the array elements of length 4 =
4
3
2
1
The sorted array is:
1
2
3
4