Loading
View RSS Feed

Angad Kumar Shukla's blog

Algorithm For Radix Sort

Rating: 9 votes, 3.89 average.
Here is an Algorithm for Radix sort.

Radix (item [], N) /* item is an array of size N */
{
/*Q is an array of Circular Queue of size 10;*/
Initialize array Q;
Find out the maximum element among the elements of the input array;
Count the digit of the maximum element and store the value into pass;
Initialize div by 1;
For (I=1; I<=pass; I++)
{
/*inserting the elements into queue*/
For (J=0; J<N; J++)
{
Set remainder is equals to item [J] %( div*10);
Update remainder by (remainder/div);
Insert (&Q [remainder], item [J]);
}
Update div by (div*10);
/*deleting the elements from the queue and place them into the array*/
For (J=0, index=0; J<10; J++) While (! Isempty (&Q [J])) item [index++] = Delete (&Q [J]);
}
}

Submit "Algorithm For Radix Sort" to Digg Submit "Algorithm For Radix Sort" to del.icio.us Submit "Algorithm For Radix Sort" to StumbleUpon Submit "Algorithm For Radix Sort" to Google

Updated 02-12-2011 at 08:32 PM by Harsh

Categories
Data Structure

Comments

  1. sonuaks's Avatar
    i have tried implementing with the help of your algorithm.
    Code:
    #include<stdio.h>
    #include<conio.h>
    
    typedef struct queue
    {
       int front,rear;
       int item[10];
    }q;
    
    void enqueue(q* qp,int val)
    {
       (qp)->rear++;
       (qp)->item[(qp)->rear]=val;
       return;
    }
    int dequeue(q* qp)
    {
       int val;
       val=(qp)->item[(qp)->front];
       (qp)->front++;
       return val;
    }
    int empty(q* qp)
    {
       if((qp)->rear<(qp)->front)
    	  return 1;
       return 0;
    }
    void radix(int*a,int m,int n)
    {
       q qu[10];
       int i,j,r,d=1,k;
       for(i=1;i<=m;i++)
       {
    	  for(j=0;j<10;j++)
    	  {
    		 qu[j].rear=-1;
    		 qu[j].front=0;
    	  }
    	  for(j=0;j<n;j++)
    	  {
    		 r=a[j]%(d*10);
    		 r=r/d;
    		 enqueue(&qu[r],a[j]);
    	  }
    	  d*=10;
    	  k=0;
    	  for(j=0;j<10;j++)
    	  {
    		  while(empty(&qu[j])==0)
    			a[k++]=dequeue(&qu[j]);
    	  }
       }
       return;
    }
    void main()
    {
       int a[10],i,no,max=a[0],count=0;
       clrscr();
       printf("\n\n Enter no of elements..");
       scanf("%d",&no);
       printf("\n\n Enter the elements..");
       for(i=0;i<no;i++)
       {
    	  scanf("%d",&a[i]);
    	  if(a[i]>max)
    		 max=a[i];
       }
       while(max>0)
       {
    	  max=max/10;
    	  count++;
       }
       radix(a,count,no);
       printf("\n\n The sorted elements are..");
       for(i=0;i<no;i++)
    	  printf("%d\t",a[i]);
       getch();
    }



Disclaimer: Users of techforum4u.com are responsible for ensuring that any material they post (article, blog posts, images or other mulitimedia content) does not violate or infringe upon the copyright, patent, trademark, or any personal or proprietary rights of any third party, and is posted with the permission of the owner of such rights.Anyone who violates these rules may have their access privileges removed without warning.