Data Structure

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 sorts process the integer representations starting from the least significant digit and move the processing towards the most significant digit.

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.

```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;

}

}

}

```

```#include<stdio.h>

#include<conio.h>

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]);

}

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

{

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

}

printf("\n");

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

{

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

}

printf("\n");

getch();

}

{

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

```