Friday, April 15, 2011

Radix Sort


import java.util.*;
class radixsort
{
                static void sort(int a[],int n)
    {
                   int large, num,l,d=1;
                   int bucket[][]=new int[10][10];
                   int b[]=new int[10];
                   large=a[0];
                   for(int i=1;i<n;i++)
                   {
                                  if(large<a[i])
                                  large=a[i];                        
                }
                   num=0;
       while(large>0)
                {
                                num++;
                                large=large/10;
                    }
                for(int p=0;p<num;p++)
        {
                                   for(int k=0;k<10;k++)
                                    b[k]=0;
                               
                                   for(int i=0;i<n;i++)
                                   {

                                                  l=(a[i]/d)%10;
                                                  bucket[l][b[l]++]=a[i];
                       }
                                int i=0;
                                for(int k=0;k<10;k++)
                                {
                                                for(int j=0;j<b[k];j++)
                                                {
                                                                a[i++]=bucket[k][j];
                                                }
                                }
                                d=d*10;
                }
  }
                public static void main(String args[])
                {
                                int a[]=new int[10];
                                Scanner s=new Scanner(System.in);
                                System.out.println("Enter the list");
                                for(int i=0;i<10;i++)
                                {
                                                a[i]=s.nextInt();
                                }
                    sort(a,10);
                                System.out.println("The sorted array is ");
                                for(int i=0;i<10;i++)
                                {
                                                System.out.println(a[i]);
                                }
                }
}

Output:-

Enter the list
538
462
12
96
4
32
756
42
69
10
The sorted array is
4
10
12
32
42
69
96
462
538
756
Press any key to continue...