Implementation of Radix Sort

AIM:

          To write a C program to implement radix sort

ALGORITHM:

            Step 1: Start the program.

Step 2: Each key is first figuratively dropped into one level of buckets                                            corresponding to the value of the rightmost digit.

Step 3: Each bucket preserves the original order of the keys as the keys are

            dropped into the bucket.

Step 4: There is a one-to-one correspondence between the number of buckets and

            the number of values that can be represented by a digit.

Step 5: Then, the process repeats with the next neighboring digit until there are no

            more digits to process. In other words:

i)                    Take the least significant digit of each key.

ii)                  Group the keys based on that digit, but otherwise keep the  

original order of keys. 

iii)                Repeat the grouping process with each more significant digit.

Step 6: Stop the program.

PROGRAM

#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++ )

{

printf("\tArray[%d] = ",i);

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

}

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

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

{

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

}

printf("\n");

radix_sort(array,n);

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

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

{

printf("%8d", 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

Enter the number of elements to be sorted:7

Enter the elements to be sorted:

 Array [0] = 777

Array [1] = 269

Array [2] = 158

Array [3] = 341

Array [4] = 265

Array [5] = 989

Array [6] = 506

Array Before Radix Sort:       777      269      158      341      265      989      506

Array After Radix Sort:          158      265      269      341      506      777      989

RESULT: Thus a C program is written to implement radix sort and executed

                  successfully