Sunday, 29 April 2012

Heap Sort with left curtailment in Java (Best)

import java.io.*;

class HeapSortLC 
{
 static int[] a;
 static int limit;
 static int constant=1;
 static int c=0,m=0; //variables to keep track of comparisons and moves

 public static void reHeapLightBubble(int k)
 {  
  if( 2*k+constant > a.length-1)
   return;

  if( 2*k+(constant+1) > a.length-1)
  {
   c++;
   if(a[k]>a[2*k+constant])
   {
    swap(k,2*k+constant);
    reHeapLightBubble(2*k+constant);  
   }
   return;
  }
  
  c+=2;

  if(a[2*k+constant]<a[k] || a[2*k+(constant+1)]<a[k])
  {
   c++;
   if(a[2*k+constant]<a[2*k+(constant+1)])
   {
    swap(k,2*k+constant);
    reHeapLightBubble(2*k+constant);
   }
   else
   {
    swap(k,2*k+(constant+1));
    reHeapLightBubble(2*k+(constant+1));
   }
   return;
  }
 }

 public static void swap(int x, int y)
 {
  int temp = a[x];
  a[x] = a[y];
  a[y] = temp;
  m+=3;
 }

 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(",");

   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");
   }  
     
   //Main logic of heap sort with left curtailment     

   for(int i=a.length-1; i>=0; i--)
   {
     reHeapLightBubble(i);
   }

   constant--;

   for(limit=1; limit<a.length-1; limit++)
   {
    reHeapLightBubble(limit);
    constant--;
   }
   
   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();
  }
 }
}

No comments:

Post a Comment

Your comments are very much valuable for us. Thanks for giving your precious time.