package basicAlgorithm; import java.io.IOException; public class ArraySort { private int[] array; private int array_len; public static int count = 0; public static int count2 = 0; public ArraySort(String filename) throws IOException { super(); array = new int[10000]; array_len = ArrayFormation.readFileToArray(array, 10000, filename); } /* * currently just choose first element in the partition as pivot */ static public int choosePivot(int[] array, int lowIndex, int highIndex) { // choose first one as Pivot, do nothing // choose last one as Pivot, swap the last one and first one; //int tmp = array[lowIndex]; // // array[lowIndex]=array[highIndex]; // // array[highIndex]=tmp; // // // choose the median of first, last and middle(left middle if the // array // // is even length) // int midIndex = (highIndex + lowIndex) / 2; // if (array[lowIndex] < array[midIndex] // && array[midIndex] < array[highIndex] // || array[highIndex] < array[midIndex] // && array[midIndex] < array[lowIndex]) { // // midIndex is median // array[lowIndex] = array[midIndex]; // array[midIndex] = tmp; // } else if (array[midIndex] < array[highIndex] // && array[highIndex] < array[lowIndex] // || array[lowIndex] < array[highIndex] // && array[highIndex] < array[midIndex]) { // // highIndex is median // array[lowIndex] = array[highIndex]; // array[highIndex] = tmp; // }// lowIndex is median, don't do anything // return array[lowIndex]; } public static void quickSort(int[] array, int lowIndex, int highIndex) { // this.printArray(); // System.out.println("low:high="+lowIndex+":"+highIndex); if (lowIndex >= highIndex) return; count2 += (highIndex - lowIndex); int i = lowIndex + 1; int pivot = choosePivot(array, lowIndex, highIndex); int tmp = 0; for (int j = lowIndex + 1; j <= highIndex; j++) { count++; // compare array[j] and pivot, see if needs swap if (array[j] < pivot) { // if there is nothing

= highIndex) return; count2 += (highIndex - lowIndex); int i = lowIndex + 1; int pivot = choosePivot(array, lowIndex, highIndex); int pivot2 = choosePivot(array2, lowIndex, highIndex); int tmp = 0; int tmp2 = 0; for (int j = lowIndex + 1; j <= highIndex; j++) { count++; // compare array[j] and pivot, see if needs swap if (array[j] < pivot) { // if there is nothing