import java.io.*;
class ShellSort 
{
 public static void main(String[] args) 
 {
  try
  {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.print("Enter name of the source file: ");
   FileReader fr =new FileReader(br.readLine());
   char[] buffer = new char[2048];
   int len = fr.read(buffer);
   String data = new String(buffer,0,len);
   String[] element = data.split(",");
   int[] a = new int[element.length];
   System.out.println("\n\nBefore Sorting: ");
   for(int i=0; i<a.length; i++)
   {
    a[i] = Integer.parseInt(element[i]);
    System.out.print(a[i]+"\t");
   }
   int c=0,m=0; //variables to keep track of comparisons and moves
   //Skips for shell sort   
   System.out.print("\nEnter number of skips (Shell Sort): ");   
   int[] skips = new int[Integer.parseInt(br.readLine())];
   
   System.out.println("Enter skips (the last skip value must be 1): ");
   for(int i=0; i<skips.length; i++)
   {
    skips[i] = Integer.parseInt(br.readLine());
   }
   
   //Main logic of shell sort
   
   for(int x=0; x<skips.length; x++)
   {
    int gap=skips[x];
    for(int start=0; start<gap; start++)
    {
     for(int i=gap+start;i<a.length;i+=gap)
     {
      for(int j=start; j<i; j+=gap)
      { 
       c++;
       if(a[i]<a[j])
       {
        int temp = a[i];
        for(int k=i; k>j; k-=gap)
        {
         m++;
         a[k]=a[k-gap];
        }
        m++;
        a[j] = temp;
        break;
       }
      } 
     }   
    }    
   }  
   
   System.out.println("\n\nAfter Sorting: ");
   for(int i=0; i<a.length; i++)
   {   
    System.out.print(a[i]+"\t");
   }
   System.out.println("\n\nComparisons = " + c + "\tMoves = " + m);
  }
  catch (Exception e)
  {
   e.printStackTrace();
  }
 }
}
Sunday, 29 April 2012
Shell Sort in Java
Subscribe to:
Post Comments (Atom)
 
 
No comments:
Post a Comment
Your comments are very much valuable for us. Thanks for giving your precious time.