Radix Sort

C program to sort an array elements using Radix Sort

#include<stdio.h>

#include<stdlib.h>

struct node

{

    int info ;

    struct node *link;

};

typedef struct node * NODE;

NODE bucket[10];

int n, a[20];

int largest()

{

    int i, large = a[0];

    for(i=0;i<n;i++)                        /*First find the largest number in the array*/

    {

        if(a[i] > large)

            large = a[i];

    }

    return large;

}

void insert_rear(int item, int rem)

{

      NODE cur, tmp;

      tmp = (NODE)malloc(sizeof(struct node));

      tmp->info = item;

      tmp->link = NULL;

      if(bucket[rem] == NULL)

      {

            bucket[rem] = tmp;

            return;

      }

      else

      {

           cur = bucket[rem];

           while(cur->link != NULL)

          {

                 cur = cur->link;

           }

           cur->link = tmp;

      }

}

void radix_sort()

{

        NODE p;

        int i, m,k, large, pass = 0, rem, divisor=1, j;

        large = largest();      /*largest number in the array*/

        printf("\nLargest Element is %d", large);

        while(large != 0)           /*Finds number of digits in the largest number*/

        {

            pass++;

            large = large/10 ;

        }

        printf("\nNumber of passes are %d", pass);

        for(m=1; m<=pass; m++)

        {

               printf("\n\n::::Pass %d::::", m);

               for(i=0;i<=9;i++)           /*initialize the buckets: Total 9 buckets*/

                      bucket[i] = NULL;

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

               {

                     rem = (a[i] / divisor) %10;

                     insert_rear(a[i], rem);

               }

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

              {

                    printf("\nbucket(%d) -> ",i);

                    p = bucket[i];

                    while(p!=NULL)

                   {

                           printf("%d ",p->info);

                           p = p->link;

                    }

              }

            /*Taking the elements of linked lists in array*/

             i = 0;

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

             {

                  p = bucket[k];

                  while(p!=NULL)

                 {

                      a[i++] = p->info;

                      p = p->link;

                 }

            }

            divisor = divisor*10;

        }

}

void main()

{

    int i;

    printf("\nEnter the number of elements in the list : ");

    scanf("%d",&n);

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

    {

        printf("\nEnter element %d : ",i+1);

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

    }

    printf("\nUnsorted list is :\n");

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

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

    radix_sort();

    printf("\nSorted list is :\n");

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

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

}

Output:

Enter the number of elements in the list : 10

Enter element 1 : 179

Enter element 2 : 208

Enter element 3 : 306

Enter element 4 : 93

Enter element 5 : 859

Enter element 6 : 984

Enter element 7 : 55

Enter element 8 : 9

Enter element 9 : 271

Enter element 10 : 33

Unsorted list is :

179   208   306   93   859   984   55   9   271   33

Largest Element is 984

Number of passes are 3

::::Pass 1::::

bucket(0) ->

bucket(1) -> 271

bucket(2) ->

bucket(3) -> 93 33

bucket(4) -> 984

bucket(5) -> 55

bucket(6) -> 306

bucket(7) ->

bucket(8) -> 208

bucket(9) -> 179 859 9

::::Pass 2::::

bucket(0) -> 306 208 9

bucket(1) ->

bucket(2) ->

bucket(3) -> 33

bucket(4) ->

bucket(5) -> 55 859

bucket(6) ->

bucket(7) -> 271 179

bucket(8) -> 984

bucket(9) -> 93

::::Pass 3::::

bucket(0) -> 9 33 55 93

bucket(1) -> 179

bucket(2) -> 208 271

bucket(3) -> 306

bucket(4) ->

bucket(5) ->

bucket(6) ->

bucket(7) ->

bucket(8) -> 859

bucket(9) -> 984

Sorted list is :

9   33   55   93   179   208   271   306   859   984