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.