C :
--------------------------------------------------------------------------
/* RADIX SORT */
/* RADIX.C*/
# include<stdio.h>
# include<malloc.h>
# include<stdlib.h>
struct node
{
int data ;
struct node *next;
};
typedef struct node node1;
node1 *first;
node1 *pocket[100], *pocket1[100];
void create_node(node1 *, int);
void display(node1 *);
node1 *radix_sort(node1 *);
int large(node1 * );
int numdig(int );
int digit(int , int);
void update(int, node1 *);
node1 *Make_link(int, node1 *);
/* This function create nodes and take input data */
void create_node(node1 *rec, int n)
{
int i, j, k;
for(i = 0 ; i< n; i++)
{
rec->next = (node1 *) malloc(sizeof(node1));
printf("\n First node value: %d: ", i);
scanf("%d", &rec->data);
rec = rec->next;
}
rec->data = NULL;
rec->next = NULL;
}
/* Output Function */
void display(node1 *rec)
{
while(rec != NULL)
{
printf(" %d", rec->data);
rec= rec->next;
}
}
/* This radix sort function */
node1 *radix_sort(node1 *rec)
{
node1 *r, *nex;
int poc = 0 ;
int i, j, k;
int larg = large(rec);
int m = numdig(larg);
/* These statements create pockets */
for(k = 0 ; k < 10; k++)
{
pocket[k] = (node1 *)malloc(sizeof(node1));
pocket1[k] = (node1 *)malloc(9*sizeof(node1));
}
/* These statements initialize pockets */
for(j = 1; j <= m ; j++)
{
for(i = 0 ; i < 10 ; i++)
{
pocket[i] = NULL;
pocket1[i] = NULL ;
}
r = rec ;
while(r != NULL)
{
int dig = digit(r->data, j);
nex = r->next ;
update(dig,r);
r = nex;
}
if(r!= NULL)
{
int dig = digit(r->data,j);
update(dig,r);
}
while(pocket1[poc] == NULL)
poc ++;
rec = Make_link(poc, rec);
}
return(rec);
}
/* This function finds largest number in the list */
int large(node1 *rec)
{
node1 *save ;
int p = 0;
save = rec ;
while(save != NULL)
{
if(save ->data > p)
{
p = save->data;
}
save = save->next ;
}
printf("\n Largest element: %d", p);
return(p);
}
/* This Function finds number digits in a number */
int numdig(int large)
{
int temp = large ;
int num = 0 ;
while(temp != 0)
{
++num ;
temp = temp/10 ;
}
printf("\n Number of digits of the number %d is %d\n", large, num);
return(num);
}
/* This function scarve a number into digits */
int digit(int num, int j)
{
int dig, i, k;
int temp = num ;
for(i = 0 ; i < j ; i++)
{
dig = temp % 10 ;
temp = temp / 10 ;
}
printf("\n %d digit of number %d is %d", j, num, dig);
return(dig);
}
/* This function updates the pockets value */
void update(int dig, node1 *r)
{
if(pocket[dig] == NULL)
{
pocket[dig] = r ;
pocket1[dig] = r ;
}
else
{
pocket[dig]->next = r ;
pocket[dig] = r ;
}
r->next = NULL;
}
/* This function create links between the nodes */
node1* Make_link(int poc , node1 *rec)
{
int i, j, k;
node1 *pointer;
rec = pocket1[poc];
for(i = poc +1 ; i< 10 ; i++)
{
pointer = pocket[i-1];
if(pocket[i] != NULL)
pointer->next= pocket1[i];
else
pocket[i] = pointer ;
}
return(rec);
}
/* Main function */
void main()
{
node1 *start, *pointer;
int number;
printf("\n Input the number of elements in the list:");
scanf("%d", &number);
start = (node1 *)malloc(sizeof(node1));
create_node(start, number);
printf("\n Given list is as follows \n");
display(start);
start = radix_sort(start);
printf("\n Sorted list is as follows:\n");
display (start);
}
-------------------------------------------------------------------------
C++
-------------------------------------------------------------------------
// RADIX SORT
// RADIX.CPP
#include<iostream.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
typedef struct node node1;
class radix
{
public:
node1 *first;
node1 *pocket[100], *pocket1[100];
public:
void create_node(node1 *, int);
void display(node1 *);
node1 *radix_sort(node1 *);
int large(node1 * );
int numdig(int );
int digit(int , int);
void update(int, node1 *);
node1 *Make_link(int, node1 *);
};
// This function create nodes and take input data
void radix :: create_node(node1 *rec, int n)
{
for( int i = 1 ; i<= n; i++)
{
rec->next = (node1 *) malloc(sizeof(node1));
cout<<"\n First node value:"<<i<<":";
cin>>rec->data;
rec = rec->next;
}
rec->next = NULL;
}
// Output Function
void radix :: display(node1 * rec)
{
while(rec)
{
cout<<" "<<rec->data;
rec= rec->next;
}
getch();
}
// This radix sort function
node1 * radix :: radix_sort(node1 *rec)
{
int larg = large(rec);
int m = numdig(larg);
// These statements create pockets
for(int k = 0 ; k < 10; k++)
{
pocket[k] = (node1 *)malloc(sizeof(node1));
pocket1[k] = (node1 *)malloc(9*sizeof(node1));
}
// These statements initialize pockets
for(int j = 1; j <= m ; j++)
{
for(int i = 0 ; i < 10 ; i++)
{
pocket[i] = NULL;
pocket1[i] = NULL ;
}
node1 *r = rec ;
while(r != NULL)
{
int dig = digit(r->data, j);
node1 *nex = r->next ;
update(dig,r);
r = nex;
}
if(r!= NULL)
{
int dig = digit(r->data,j);
update(dig,r);
}
int poc = 0 ;
while(pocket1[poc] == NULL)
poc ++;
rec = Make_link(poc, rec);
cout<<"\n Newly ordered list:\n";
display(rec);
}
return(rec);
}
// This function finds largest number in the list
int radix :: large(node1 *rec)
{
node1 *save ;
int p = 0;
save = rec ;
while(save != NULL)
{
if(save ->data > p)
p = save->data;
save = save->next ;
}
cout <<"\n Largest element:"<<p;
return(p);
}
// This Function finds number digits in a number
int radix :: numdig(int large)
{
int temp = large ;
int num = 0 ;
while(temp != 0)
{
++num ;
temp = temp/10 ;
}
cout <<"\n Number of digits of the number "<<large<<" is "<<num ;
return(num);
}
// This function scarve a number into digits
int radix :: digit(int num, int j)
{
int dig ;
int temp = num ;
for( int i = 0 ; i < j ; i++)
{
dig = temp % 10 ;
temp = temp / 10 ;
}
cout<<"\n";
cout <<j <<" digit of number "<<num <<" is "<<dig;
getch();
return(dig);
}
// This function updates the pockets value
void radix :: update(int dig, node1 *r)
{
if(pocket[dig] == NULL)
{
pocket[dig] = r ;
pocket1[dig] = r ;
}
else
{
pocket[dig]->next = r ;
pocket[dig] = r ;
}
r->next = NULL;
}
// This function create links between the nodes
node1* radix :: Make_link(int poc , node1 *rec)
{
node1 *pointer;
rec = pocket1[poc];
for(int i = poc +1 ; i< 10 ; i++)
{
pointer = pocket[i-1];
if(pocket[i] != NULL)
pointer->next= pocket1[i];
else
pocket[i] = pointer ;
}
return(rec);
}
// Main function
void main()
{
radix rad;
node1 *start, *pointer;
int number;
cout<<"\n Input the elements of the list :\n";
cout<<"\n Input the number of elements in the list:";
cin>>number;
start = (node1 *)malloc(sizeof(node1));
rad.create_node(start, number);
cout<<"\n Given list is as follows \n";
rad.display(start);
start = rad.radix_sort(start);
cout<<"\n Sorted list is as follows:\n";
rad.display (start);
}
23:18
vishal pandya
