Friday, August 31, 2012

C Program for Radix Sort

/**************************************************************************
////////////////// -*-  Program on Radix Sort  -*- \\\\\\\\\\\\\\\\\\\\\\\\
//////////////// --*-- By.:Vikrantsingh.M.Bisen --*-- \\\\\\\\\\\\\\\\\\\\\
***************************************************************************/
#include<iostream.h>
#include<math.h>
#include<conio.h>
int bucket[10][10];
int top[10];
int array[10],temp[10];
int i,j,k,size,length;
void initialize()
{
    for(i=0;i<10;i++)
    top[i]=0;
    for(i=0;i<10;i++)
    for(int r=0;r<10;r++)
    bucket[i][r]=0;
}
void copy_to_bucket()
{
    for(i=0;i<size;i++)
    {
     int lsb=temp[i]%10;
     bucket[lsb][top[lsb]]=array[i];
     top[lsb]++;
    }
    //---------Printing
    cout<<"\nBucket Contaion.:\n  ";
    for(i=0;i<10;i++)
    {for(int h=0;h<10;h++){ cout<<" "<<bucket[i][h];}cout<<endl;}
    cout<<"\n TOP Contain.:\n ";
    for(i=0;i<10;i++)
    cout<<" "<<top[i];

}
void copy_to_array()
{
    int k=0;
    for(i=0;i<10;i++)
    {
     int j=0;
     while(j<top[i])
     {
      array[k]=bucket[i][j];
      k++;j++;
     }
    }
    cout<<endl<<"Array Contain.:\n";
    for(i=0;i<size;i++)
    cout<<" "<<array[i];
}
void find_max_length()
{
  int y=1;
  length=0;
  for(i=0;i<size;i++)
  {
   int x=array[i];
   y=0;
   while(x!=0)
   {y++;x=x/10;}
   if(y>length)length=y;
  }

}
void main()
{
  clrscr();
  cout<<"Enter Size";
  cin>>size;
  for(int i=0;i<size;i++)
   cin>>array[i];
//  -------------
  for(i=0;i<size;i++)
  temp[i]=array[i];
  //-------
  find_max_length();
  //--------
  int p=1;
  for(int m=0;m<length;m++)
  {
    initialize();
    //-------assign from array to bucket
    copy_to_bucket();
    //-------assign from bucket to array
    copy_to_array();
    //---
   getch();
    for(i=0;i<size;i++)
    temp[i]=array[i]/pow(10,p);p++;
  }
 cout<<"\nSorted Array.:";
 for(i=0;i<size;i++)
 cout<<"  "<<array[i];
 getch();
}

No comments:

Post a Comment