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();
}
}
}
Sunday, 29 April 2012
Quick 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.