Radix Sort | Data Structure

Complete Program of Radix Sort In C:

Radix Sort: In radix sort first we find the largest number from the given number and then count the number of digit that contain the largest number. In this algorithm we consider 10 columns 0-9 because each digit must lies between 0-9.In this process every time we will find first unit place digit,tens place,hundred place digit and so on... on the basis of that digit we will place that digit in the particular column .All the process is perform in a matrix so we will create matrix of [n][m] and by default place -999 into matrix. This process is perform until we are not getting sorted list.After that we will convert matrix into an array.

So for doing this process we will perform following steps:

1. Find Big number.

2. Count number of digit of N numbers.

3. Find Position of digit.

4. Fill matrix with any number which are not in given array like -999

5. Matrix is converted into an array.

And than finally we get sorted list.

#include<conio.h>

#include<stdio.h>

void radixsort(int a[],int n);

int bigno(int a[20],int n);

int numdigit(int big);

void fillmat(int m[20][10],int n);

void makearray(int m[20][10],int a[20],int n);

void main()

{

int a[20]={2134,231,4513,177,6355,233,5},n,i;

//printf("Enter the value of n:");

//scanf("%d",&n);

n=7;

radixsort(a,n);   // Call Radix Sort Function

getch();

}

// Radix Sort Function

void radixsort(int a[20],int n)

{

int big,k,col,m[20][10],row,i,j;

big= bigno(a,n);

//printf("Big number is:",big);

k= numdigit(big);

//printf("%d",k);

    printf("\n");

    for(i=1;i<=k;i++)

{

    fillmat(m,n);

    for(row=0;row<=n-1;row++)

        {

           col=poss(a[row],i);

           m[row][col]=a[row];

        }

        makearray(m,a,n);

}

   //print matrix

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

{

{

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

}

}

}

// Function for finding Big Number

int bigno(int a[20],int n)

{

int i,big;

big=a[0];

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

{

if(a[i]>big)

{

big=a[i];

}

}

return(big);

}

// Function for find number of digit in big number

int numdigit(int big)

{

int c=0;

while(big>0)

{

c++;

big=big/10;

}

return(c);

}

// Function for fill matrix

void fillmat(int m[20][10],int n)

{

int i,j;

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

{

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

{

m[i][j]=-999;

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

}

printf("\n");

}

}

// Function for find position of digit

int poss(int n,int pos)

{

int digit;

while(pos>=0)

{

digit=n%10;

n=n/10;

pos--;

}

return(digit);

}

// Function for convert matrix into array

void makearray(int m[20][10],int a[20],int n)

{

    int i,j,k=0;

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

    {

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

        {

            if(m[j][i]!=-999)

            {

                a[k]=m[j][i];

                k++;

            }

        }

    }

}