Sunday, 29 April 2012

Heap Sort with Partial Heaping in Java

import java.io.*;

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

 public static void reHeap(int k)
 {  
  if( 2*k+1 > limit)
   return;

  if( 2*k+2 > limit)
  {
   c++;
   if(a[k]<a[2*k+1])
   {
    swap(k,2*k+1);
    reHeap(2*k+1);  
   }
   return;
  }
  
  c+=2;
  if(a[2*k+1]>a[k] || a[2*k+2]>a[k])
  {
   c++;
   if(a[2*k+1]>a[2*k+2])
   {
    swap(k,2*k+1);
    reHeap(2*k+1);
   }
   else
   {
    swap(k,2*k+2);
    reHeap(2*k+2);
   }
   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 partial heaping
   limit=a.length-1;
   reHeap(limit);
   swap(0,limit);
   
   limit--;

   for(; limit>0; limit--)
   {
    reHeap(0);
    swap(0,limit);
   }
   
   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.