Radix Sort Sorting Technique and C Program

Radix Sort

Consider an array  A= { 54, 33, 25, 17, 09, 37, 13 }.

In radix sort traverse array from left to right. Check maximum no. of digits in the array.  In the above case, it is 2 so it will have 2-pass i.e, in the second pass information will be in sorted.

Traverse array from left to right,  check unit place of  each number in the array.  Unit place of 54 is 4, so put 54 in bucket 4.  Similarly, unit place of 33 is 3, so put 33 in buctet 3.  Similarly, check all the numbers in the array and put those numbers in their respective buckets

Bucket	Pass-1	Pass-2
0
1
2
3	33,13
4	54
5	25
6
7	17,37
8
9	09

Now  Merge the Output of pass-1.  Result is as follows A= {33,13,54, 25, 17, 37, 09}

Now tranverse output of Pass-1 from left to right.  Now check 10^th place of each number in the array.  10^th place of 33 is 3, put 33 in bucket 3.  Similarly, 10^th place of 13 is 1, put 13 in bucket 1.  Similarly, check all the numbers in the array and put those numbers in their respective buckets.

Bucket	Pass-1	Pass-2
0		09
1		13,17
2		25
3	33,13	33,37
4	54
5	25	54
6
7	17,37
8
9	9

Now Merge the output of pass-2.  Result is as follows A= {09, 13, 17, 25, 33, 37, 54}

Note: if Maximum no. of digits is 3 then there will be 3 passes. If 4-digits, 4 passes etc.

The same can be done using the following calculation.

Consider an array  A= { 54, 33, 25, 17, 09, 37, 13 }.

For Pass-1 Calculation (unit place)

 

     54/10⁰  =  54/1 =  54 =  54%10 =  4       Put 54 in bucket 4

     33/10⁰  =  33/1 =  33 =  33%10 =  3       Put 33 in bucket 3

       25/10⁰  =  25/1 =  25 =  25%10 =  5       Put 25 in bucket 5

     17/10⁰  =  17/1 =  17 =  17%10 =  7       Put 17 in bucket 7

     09/10⁰  =  09/1 =  09 =  09%10 =  9       Put 09 in bucket 9

     37/10⁰  =  37/1 =  37 =  37%10 =  7       Put 37 in bucket 7

     13/10⁰  =  13/1 =  13 =  13%10 =  3       Put 13 in bucket 3

Bucket	Pass-1	Pass-2
0
1
2
3	33,13
4	54
5	25
6
7	17,37
8
9	09

Merge output of pass-1 i.e., A= {33,13,54, 25, 17, 37, 09}

For Pass-2 Calculation (10^th  place).

 

     33/10¹  =  33/10 =  3 =  3%10 =  3       Put 33 in bucket 3

     13/10¹  =  13/10 =  1 =  1%10 =  1       Put 13 in bucket 1

       54/10¹  =  54/10 =  5 =  5%10 =  5       Put 54 in bucket 5

     25/10¹  =  25/10 =  2 =  2%10 =  2       Put 25 in bucket 2

     17/10¹  =  17/10 =  1 =  1%10 =  1       Put 17 in bucket 1

     37/10¹  =  37/10 =  3 =  3%10 =  3       Put 37 in bucket 3

     09/10¹  =  09/10 =  0 =  0%10 =  0       Put 09 in bucket 0

Bucket	Pass-1	Pass-2
0		09
1		13,17
2		25
3	33,13	33,37
4	54
5	25	54
6
7	17,37
8
9	09

Now Merge the output of pass-2.  Result is as follows A= {09, 13, 17, 25, 33, 37, 54}

C Program for radix sort.

#include<stdio.h>

#include<math.h>

struct node

{

   int data;

   struct node *link;

};

struct node * createnodes(int n)

{

  int i;

  struct node *p,*first,*temp;

  printf("Enter elements\n");

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

  {

    p= (struct node *) malloc(sizeof(struct node));

    scanf("%d", &p->data);

    p->link = NULL;

    if (i==0)

    {

      first=p;

    }

    else

    {

      temp=first;

      while (temp->link!=NULL)

      {

            temp=temp->link;

      }

      temp->link=p;

    }

  }

  return first;

}

void displaynodes(struct node *f)

{

  struct node *temp;

  temp=f;

  while (temp!=NULL)

  {

    printf("%d-->",temp->data);

    temp=temp->link;

  }

  printf("Null\n");

}

int MaxDigits(struct node *f)

{

  struct node *temp;

  int max,ct,n;

  temp=f;

  max=0;

  while (temp!=NULL)

  {

    n=temp->data;

    ct=0;

    while(n>0)

    {

      ct++;

      n=n/10;

    }

    if (ct>max)

    { max=ct; }

    temp=temp->link;

  }

  return max;

}

void RadixSort(struct node *f1)

{

  struct node *first,*f[10],*r[10],*temp;

  int max,i,j,k,p;

  max=MaxDigits(f1);

  first=f1;

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

  {

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

    {

      f[j]=NULL;

      r[j]=NULL;

    }

    while(first!=NULL)

    {

      temp=first;

      first=first->link;

      p=(temp->data/pow(10.0,(float)i));

      p=p%10;

      if(f[p]==NULL && r[p]==NULL)

      {

            f[p]=temp;

            r[p]=temp;

            temp->link=NULL;

      }

      else

      {

            r[p]->link=temp;

            temp->link=NULL;

            r[p]=temp;

      }

    }

    first=f[0];

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

    {

      if (first==NULL && f[k]==NULL)

            first=NULL;

      else if (first==NULL && f[k]!=NULL)

            first=f[k];

      else

      {

            temp=first;

            while(temp->link!=NULL)

             { temp=temp->link; }

            temp->link=f[k];

      }

    }

    printf("Result of Pass - %d  : ",i+1);

    displaynodes(first);

  }

}

void main()

{

  int n;

  struct node *first;

  clrscr();

  printf ("Enter size of array/Linked list \n");

  scanf("%d",&n);

  first = createnodes(n);

  printf("Printing the elements from LL before sorting\n");

  displaynodes(first);

  RadixSort(first);

  getch();

}