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
| Class | Sorting algoritdm |
| Data structure | Array |
| Worst case performance | O(K N) |
| Worst case space complexity | O(K N) |