Sunday, 29 April 2012

Quick Sort in Java

import java.io.*;

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

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

 public static void quickSort(int lb, int ub)
 {
  if(lb>=ub)
   return;

  int down = lb;
  int up = ub;
  int pivot_index = findPivotIndex(lb,ub);

  while(down<up)
  {   
   while(a[down]<=a[pivot_index] && down<up)
   {
    c++;
    down++;
   }
   
   while(a[up]>a[pivot_index])
   {
    c++;
    up--;
   }

   if(down<up)
    swap(down,up);
  }

  if(pivot_index!=up)
   swap(pivot_index,up);

  quickSort(lb,up-1);
  quickSort(up+1,ub);
 }

 public static int findPivotIndex(int lb, int ub)
 {
  int x1=a[lb];
  int x2=a[(lb+ub)/2];
  int x3=a[ub];

  if(x1>x2 && x1<x3 || x1<x2 && x1>x3)
   return lb;

  if(x2>x1 && x2<x3 || x2<x1 && x2>x3)
   return (lb+ub)/2;

  if(x3>x2 && x3<x1 || x3<x2 && x3>x1)
   return ub;

  return lb;
 }

 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");
   }  
     
   quickSort(0,a.length-1); //call to quick Sort  
   
   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.