Thursday 10 November 2016

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



No comments:

Post a Comment