Radix sort

Radix sort was developed for sorting large integers, but it treats an integer as a string of digits, so it is really a string sorting algorithm.
Radix sort is a non-comparative sorting algorithm that sorts data with keys by grouping keys by the individual digits which share the same significant position and value.
Radix Sort arranges the elements in order by comparing the digits of the numbers.





LSD radix sort

Least-significant-digit-first radix sort.
LSD radix sorts process the integer representations starting from the least significant digit and move the processing towards the most significant digit.




MSD radix sort

Most-significant-digit-first radix sort.
MSD radix sort starts processing the keys from the most significant digit, leftmost digit, to the least significant digit, rightmost digit. This sequence is opposite that of least significant digit (LSD) radix sorts.



Algorithm of RADIX-SORT


RADIX-SORT (A ,d)

1) for i ? 1 to d;

2) do use a stable sort to sort Array A on digit i // counting sort will do the job//




c Fuction for radix sort


radix_sort(int arr[], int n)

{

	int bucket[10][5],buck[10],b[10];

	int i,j,k,l,num,div,large,passes;



	div=1;

	num=0;

	large=arr[0];



	for(i=0 ; i< n ; i++)

	{

		if(arr[i] > large)

		{

			large = arr[i];

		}

		while(large > 0)

		{

			num++;

			large = large/10;

		}

		for(passes=0 ; passes < num ; passes++)

		{

			for(k=0 ; k< 10 ; k++)

			{

				buck[k] = 0;

			}

			for(i=0 ; i< n  ;i++)

			{

				l = ((arr[i]/div)%10);

				bucket[l][buck[l]++] = arr[i];

			}



			i=0;

			for(k=0 ; k < 10 ; k++)

			{

				for(j=0 ; j < buck[k] ; j++)

				{

					arr[i++] = bucket[k][j];

				}

			}

			div*=10;

		}

	}

}




Implementation of radix sort


#include<stdio.h>

#include<conio.h>

 

radix_sort(int array[], int n);

void main()

{

	int array[100],n,i;

	clrscr();

	printf("Enter the number of elements to be sorted: ");

	scanf("%d",&n);

	printf("\nEnter the elements to be sorted: \n");

	for(i = 0 ; i < n ; i++ )

	{

		scanf("%d",&array[i]);

	}



	printf("\nBefore Radix Sort:");

	for(i = 0; i < n; i++)

	{

		printf("%d\t", array[i]);

	}

	printf("\n");

	radix_sort(array,n);

	printf("\nArray After Radix Sort: ");  //Array After Radix Sort

	for(i = 0; i < n; i++)

	{

		printf("%d\t", array[i]);

	}

	printf("\n");

	getch();

}

 

radix_sort(int arr[], int n)

{

	int bucket[10][5],buck[10],b[10];

	int i,j,k,l,num,div,large,passes;



	div=1;

	num=0;

	large=arr[0];



	for(i=0 ; i < n ; i++)

	{

		if(arr[i] > large)

		{

			large = arr[i];

		}

		while(large > 0)

		{

			num++;

			large = large/10;

		}

		for(passes=0 ; passes < num ; passes++)

		{

			for(k=0 ; k < 10 ; k++)

			{

				buck[k] = 0;

			}

			for(i=0 ; i < n  ;i++)

			{

				l = ((arr[i]/div)%10);

				bucket[l][buck[l]++] = arr[i];

			}



			i=0;

			for(k=0 ; k< 10 ; k++)

			{

				for(j=0 ; j < buck[k] ; j++)

				{

					arr[i++] = bucket[k][j];

				}

			}

			div*=10;

		}

	}

}




OUTPUT





Explaination

Consider a group of numbers. It is given by the list:
123, 002, 999, 609, 111
STEP1:
Sort the list of numbers according to the ascending order of least significant bit. The sorted list is given by:
111, 002, 123, 999, 609
STEP2:
Then sort the list of numbers according to the ascending order of 1st significant bit. The sorted list is given by:
609, 002, 111, 123, 999
STEP3:
Then sort the list of numbers according to the ascending order of most significant bit. The sorted list is given by:

002, 111, 123, 609, 999






Analysis Of Radix sort

Class Sorting algoritdm
Data structure Array
Worst case performance O(K N)
Worst case space complexity O(K N)



Quantitative Aptitude
Reasoning
Programming
Interview