Sorting Techniques - Radix Sort and Counting Sort


Arranging a list of elements in an order (ascending or descending) is called sorting. There are different types of sorting techniques in which one technique is better than its predecessor. In this article, I am going to discuss the two sorting techniques radix sort and counting sort with their algorithms and C programs.

Radix Sort


This is a sorting technique which comes under the category of sorting by distribution. The procedure of radix sort is as follows. Define ten auxiliary arrays Q0, Q1 …… Q9. Place the elements of the list in auxiliary array corresponding to units place of the elements. Arrange the elements in auxiliary array order i.e. from Q0 to Q9. Then, place the elements of the list in auxiliary array corresponding to tens place of the elements. Arrange the elements in auxiliary array order i.e. from Q0 to Q9. Repeat until this cannot be done. The list will get sorted. Here, auxiliary arrays are queues and list of elements is a linked list. To understand this technique clearly, let us perform radix sort on the list 20, 40, 12, 45, 67, 56, 34, 89, 54, 36.

20 40 12 45 67 56 34 89 54 36

Q0 : 20 40
Q1 :
Q2 : 12
Q3 :
Q4 : 34 54
Q5 : 45
Q6 : 56 36
Q7 : 67
Q8 :
Q9 : 89

20 40 12 34 54 45 56 36 67 89

Q0 :
Q1 : 12
Q2 : 20
Q3 : 34 36
Q4 : 40 45
Q5 : 54 56
Q6 : 67
Q7 :
Q8 : 89
Q9 :

12 20 34 36 40 45 54 56 67 89

Algorithm for Radix Sort



Input : An array a[1], a[2], …… a[n].
Output : The array a[1], a[2], …… in ascending order.

1 : START
2 : for i=1 to c do
3 : for j=1 to n do
4 : x=extract(a[j],i)
5 : enqueue(Qx,a[j])
6 : endFor
7 : for k=0 to 9 do
8 : while Qk contains at least one element do
9 : y=dequeue(Qk)
10 : insert(a,y)
11 : endWhile
12 : endFor
13 : endFor
14 : STOP

C Program for Radix Sort


Program
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
}*start=NULL;
int larger_digit()
{
struct node *p=start;
int large=0,ndigit=0;
while(p!=NULL)
{
if(p->data>large)
large=p->data;
p=p->next ;
}
while(large!=0)
{
ndigit++;
large=large/10 ;
}
return(ndigit);
}
int digit(int num,int k)
{
int digit,i;
for(i=1;i<=k;i++)
{
digit=num%10;
num=num/10;
}
return(digit);
}
void radix_sort()
{
int i,k,dig,lsig,msig;
struct node *p,*rear[10],*front[10];
lsig=1;
msig=larger_digit();
for(k=lsig;k<=msig;k++)
{
for(i=0;i<=9;i++)
{
rear[i]=NULL;
front[i]=NULL ;
}
for(p=start;p!=NULL;p=p->next)
{
dig=digit(p->data,k);
if(front[dig]==NULL)
front[dig]=p;
else
rear[dig]->next=p;
rear[dig]=p;
}
i=0;
while(front[i]==NULL)
i++;
start=front[i];
while(i<9)
{
if(rear[i+1]!=NULL)
rear[i]->next=front[i+1];
else
rear[i+1]=rear[i];
i++;
}
rear[9]->next=NULL;
}
}
void main(void)
{
struct node *temp,*q;
int i,n,number;
clrscr();
printf("\n Enter the number of elements in the list : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\n Enter the value of element %d in the list : ",i+1);
scanf("%d",&number);
temp=(struct node*)malloc(sizeof(struct node));
temp->data=number;
temp->next=NULL;
if(start==NULL)
start=temp;
else
{
q=start;
while(q->next!=NULL)
q=q->next;
q->next=temp;
}
}
radix_sort();
printf("\n The list after sorting is : ");
q=start;
while(q!=NULL)
{
printf("%d ",q->data);
q=q->next;
}
getch();
}

Output
Enter the number of elements in the list : 10
Enter the value of element 1 in the list : 20
Enter the value of element 2 in the list : 40
Enter the value of element 3 in the list : 12
Enter the value of element 4 in the list : 45
Enter the value of element 5 in the list : 67
Enter the value of element 6 in the list : 56
Enter the value of element 7 in the list : 34
Enter the value of element 8 in the list : 89
Enter the value of element 9 in the list : 54
Enter the value of element 10 in the list : 36
The list after sorting is : 12 20 34 36 40 45 54 56 67 89

Counting Sort


This is a sorting technique which comes under the category of sorting by distribution. The procedure of counting sort is as follows. Define a count array to store the number of times a number occurs in the given list. Modify the count array by replacing its elements with sum of elements until that element i.e. cumulative count value. Now, display elements on par with the count array values. To understand this technique clearly, let us perform counting sort on the list 10, 35, 25, 25, 40, 10, 70, 40, 25, 80 (n=10).

Input
10 35 25 25 40 10 70 40 25 80

Original Count Array
c[10]=2
c[25]=3
c[35]=1
c[40]=2
c[70]=1
c[80]=1

Modified Count Array
c[10]=2
c[25]=2+3=5
c[35]=2+3+1=6
c[40]=2+3+1+2=8
c[70]=2+3+1+2+1=9
c[80]=2+3+1+2+1+1=10=n

Display 10 until 2nd position (c[10]=2)
10 10
Display 25 until 5th position (c[25]=5)
10 10 25 25 25
Display 35 until 6th position (c[35]=6)
10 10 25 25 25 35
Display 40 until 8th position (c[40]=8)
10 10 25 25 25 35 40 40
Display 70 until 9th position (c[70]=9)
10 10 25 25 25 35 40 40 70
Display 80 until nth position (c[80]=n)
10 10 25 25 25 35 40 40 70 80

Output
10 10 25 25 25 35 40 40 70 80

Algorithm for Counting Sort



Input : An array a[1], a[2], …… a[n].
Output : An array b[1], b[2], …… b[n] i.e. input in ascending order.

1 : START
2 : for i=1 to k do
3 : c[i]=0
4 : endFor
5 : for i=1 to n do
6 : c[a[i]]=c[a[i]]+1
7 : endFor
8 : for i=1 to k do
9 : c[i]=c[i-1]+c[i]
10 : endFor
11 : for i=n to 1 do
12 : b[c[a[i]]]=a[i]
13 : c[a[i]]=c[a[i]]-1
14 : endFor
15 : STOP

C Program for Counting Sort


Program
#include<stdio.h>
#include<conio.h>
void counting_sort(int list[],int n,int list_max)
{
int count[99],i,j;
for(i=0;i<99;i++)
count[i]=0;
for(i=0;i<n;i++)
count[list[i]]=count[list[i]]+1;
printf("\n The list after sorting is : ");
for(i=0;i<=list_max;i++)
for(j=1;j<=count[i];j++)
printf("%d ",i);
}
void main(void)
{
int list[99],n,i,list_max=0;
clrscr();
printf("\n Enter the number of elements in the list : ");
scanf("%d",&n);
printf("\n Enter the elements in the list : ");
for(i=0;i<n;i++)
{
scanf("%d",&list[i]);
if(list[i]>list_max)
list_max=list[i];
}
counting_sort(list,n,list_max);
getch();
}

Output
Enter the number of elements in the list : 10
Enter the elements in the list : 10 35 25 25 40 10 70 40 25 80
The list after sorting is : 10 10 25 25 25 35 40 40 70 80


Comments

No responses found. Be the first to comment...


  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:
    Email: