package sort;/** if (the list size is greater than 1) { a. Partition the list into 2 sublists,say lowerSublist and upperSublist; b. Quick sort lowerList; c. Quick sort upperList; d. Combine the sorted lowerSublist and sorted upperSublist.
}
**/public class QuickSort{ private Comparable[] datum; public static int times; //constructor public QuickSort(){} public QuickSort(Comparable[] datum) { this.datum = datum; } //main method to invoke quickSort() as an example public static void main(String[] args)throws IOException { String inString ; StringTokenizer tokenizer; Comparable [] elements; BufferedReader in = new BufferedReader( new InputStreamReader(System.in)); //get size System.out.println("Please input the size: "); inString = in.readLine(); elements = new Integer[Integer.parseInt(inString)]; //get elements System.out.println("Enter the numbers of elements : "); inString = in.readLine(); tokenizer = new StringTokenizer(inString); for (int i =0; i<elements.length && tokenizer.hasMoreTokens();i++) { elements[i] = Integer.parseInt(tokenizer.nextToken()); } QuickSort qs = new QuickSort(elements); long startTime = System.currentTimeMillis(); qs.quickSort(); System.out.println("after sorted :"); for (int i=0;i<qs.getSize();i++) { System.out.println(qs.getDatum()[i]); } System.out.println("take time = "+(System.currentTimeMillis()-startTime)+" ms"); System.out.println("size : "+elements.length+" , cursory times : "+times); } public void quickSort() { recQuickSort(0,datum.length-1); } private void recQuickSort(int first,int last) { times++; int pivotLocation; if(first < last) { pivotLocation = partition(first,last); recQuickSort(first,pivotLocation-1); recQuickSort(pivotLocation+1,last); } } private int partition(int first,int last) { Comparable pivot; int index , smallIndex; swap(first,(first+last)/2); pivot = datum[first]; smallIndex = first; for(index=first+1;index<=last;index++) { if(datum[index].compareTo(pivot) < 0) { smallIndex++; swap(smallIndex,index); } } swap(first,smallIndex); return smallIndex; } private void swap(int first,int second) { Comparable temp; temp = datum[first]; datum[first] = datum[second]; datum[second] = temp; } public int getSize() { return this.datum.length; } public Comparable[] getDatum() { return this.datum; }}
