Sorting – Radix Sort

Sorting – Radix Sort

Radix Sort sorts the number in scans equal to the number of digits of maximum number.

eg.  45, 3, 235, 89, 150, then maximum scans = 3.

Thus radix sort operates three times.

Radix sort uses 10 queues to sort the given numbers.

• Begin with least significant digit, ending with most significant digit.
• Fetch a number from the array and place it in one of the queues depending upon its value say 2 means it is placed in node[2].  If a number already exists at that position than the correct ordered position for the new number is determined.
• Retrieve these elements from the queue from 0 to n back into array.
• Repeat this process till most significant bit.
• Display the array which is finally sorted.

Program to implement Radix Sort:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 5

struct queue
{int info;
struct queue *next;
}*node[10]={NULL};

struct queue *front=NULL,*rear=NULL;
struct queue *create()
{
struct queue *temp=(struct queue*)malloc(sizeof(struct queue));
if(temp==NULL)
{printf(“\nMemory Allocation Error!”);
exit(1);
}
return temp;
}

struct queue *makenode(int num)
{
struct queue *temp=create();
temp->info=num;
temp->next=NULL;
return temp;
}
struct queue *insert(struct queue *s,int num)
{
struct queue *ptr=s;
struct queue *temp=makenode(num);
if(s==NULL)
s=temp;
else
{while((ptr->next->info<=num) && (ptr->next!=NULL))
ptr=ptr->next;
if(temp->info<ptr->info)
{temp->next=ptr;
s=temp;
}
else
{temp->next=ptr->next;
ptr->next=temp;
}
}
return s;
}

int digits_count(int num)
{
int rmdr,quot,ct=0;
quot=num/10;
rmdr=num%10;
ct++;
while(quot!=0)
{
num=quot;
quot=num/10;
rmdr=num%10;
ct++;
}
return ct;
}

int max_element(int arr[],int n)
{
int max,i;
max=arr[0];
for(i=1;i<n;i++)
{if(arr[i]>max)
max=arr[i];
}
return max;
}

int return_ith_digit(int num,int pos)
{
int i, ndigits, rmdr;
ndigits = digits_count(num);
if(pos>ndigits)
return 0;
rmdr=num%10;
for(i=0;i<pos;i++)
{
num=num/10;
rmdr=num%10;
}
return rmdr;
}

void radixsort(int arr[], int n)
{
int i,j,digits,max,y;
int k=0,p=0;
max=max_element(arr,n);
digits = digits_count(max);
for(i=0;i<digits;i++)
{
for(j=0;j<n;j++)
{
y=return_ith_digit(arr[j],i);
node[y]=insert(node[y],arr[j]);
}
for(p=0;p<10;p++)
{
while(node[p]!=NULL)
{
arr[k++]=node[p]->info;
printf(“%d->”,node[p]->info);
node[p]=node[p]->next;
}
}
printf(“\b\b “);
}
}
void main()
{
int arr[MAX],i,n;
clrscr();
printf(“\nEnter total number of elements?”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{printf(“\nEnter number?”);
scanf(“%d”,&arr[i]);
}
radixsort(arr,n);
getch();
}