Thursday, January 14, 2010

Radix sort

What is radix sort?
  Radix Sort is an algorithm that sorts a list of numbers and comes under the category of distribution sort.
This sorting algorithm doesn't compare the numbers but distributes them, it works as follows:
1. Sorting takes place by distributing the list of number into a bucket by passing through the individual digits of a given number one-by-one beginning with the least significant part. Here, the number of buckets are a total of ten, which bare key values starting from 0 to 9.
2. After each pass, the numbers are collected from the buckets, keeping the numbers in order
3. Now, recursively redistribute the numbers as in the above step '1' but with a following reconsideration: take into account next most significant part of the number, which is then followed by above step '2'.

 Radix sort in C:
#include <conio.h>
using namespace std;
#include <iostream>
#include <math>

void radixsort(int num[],int n)
{
     int queue[10][10],inc[10],i,j,k,c,exp;
     for(i=0;i<4;i++)
     {
                exp=pow(10,i);
                for(j=0;j<10;j++)
                                 inc[j]=-1;    
                for(j=0;j<10;j++)
                {                
                                 k=(num[j]/exp)%10;
                                 inc[k]++;
                                 queue[k][inc[k]]=num[j];
                }
                for(k=0,c=0;k<10;k++)
                {
                                 j=0;
                                 if(inc[k]!=-1)
                                                  while(j<=inc[k])
                                                  {
                                                                 num[c++]=queue[k][j];
                                                                 j++;
                                                  }
                }
     }
}


Using the function

int main()
{
    int num[10];
    cout<<"Enter the elements to be sorted :\n";
    for(int i=0;i<10;i++)
            cin>>num[i];
    radixsort(num,10);
    cout<<"The elemments in sorted order are :\n";
    for(int i=0;i<10;i++)
            cout<<<"  ";
    getch();
}

0 comments:

Post a Comment