// File: Quicksort.java /** Data for Quicksort from TestSort Based on Knuth, ending in an insertion sort, pivot by middle of 3 */ public class Quicksort { public static int MAX_INSERTION_SORT = 10; // parameter to tune for speed /** * Sort with a variant of Hoare's quicksort algorithm. * @param data * array containing elements to sort * @param start * index of first element to be sorted * @param end * index of final element to be sorted */ public static void quicksort(int[ ] data, int start, int end) { // nonrecursive, efficient inner loop, // limited stack size, OK if list already sorted int pivotIndex; // Array index for the pivot element int first, last; // start, end of current part int n1, n2; // Number of elements before and after the pivot element int[] stack = new int[100]; //Stack to hold index ranges // allows 2^50 elements to be sorted! int top = -1; //Fill stack with initial values in preparation for loop if (end - start >= MAX_INSERTION_SORT) { stack[++top] = start; stack[++top] = end; } while(top >= 0) { //Get segment length & first index values last = stack[top--]; first = stack[top--]; // Partition the array, and set the pivot index. pivotIndex = partition(data, first, last); // System.out.println("Pivot index: " + pivotIndex); // TestSort.printArray(data); // Compute the sizes of the two pieces. n1 = pivotIndex - first; n2 = last - pivotIndex; // Push the n & first values of the array segments before & after // the pivotIndex onto the stack. Make sure the larger of the // two segments is pushed first. Only push a segment if its // length is > 1 if(n2 < n1) { if(n1 > MAX_INSERTION_SORT) { stack[++top] = first; stack[++top] = pivotIndex-1; } if(n2 > MAX_INSERTION_SORT) { stack[++top] = pivotIndex+1; stack[++top] = last; } } else { if(n2 > MAX_INSERTION_SORT){ stack[++top] = pivotIndex+1; stack[++top] = last; } if(n1 > MAX_INSERTION_SORT){ stack[++top] = first; stack[++top] = pivotIndex - 1; } } // end push depending on size } // end while loop for stack insertionsort(data, start, end); } // end quicksort private static int partition(int[ ] data, int first, int last) { // This version chooses pivot from first, last, mid index. // Precondition: last>first, and data from index first through last. // Postcondition: The method has selected some "pivot value" that occurs // in data[first]...data[last]. The elements of data have then been // rearranged and the method returns a pivot index so that // -- data[pivot index] is equal to the pivot; // -- each element before data[pivot index] is <= the pivot; // -- each element after data[pivot index] is >= the pivot. int mid = (first + last)/2; // pivot candidates first, mid, last int pivot = data[mid]; // first try // effectively sort first, mid, last, then swap mid to first+1 if (data[first] > pivot) { pivot = data[first]; data[first] = data[mid]; data[mid] = pivot; } if (data[last] < pivot) if (data[last] < data[first]) { // last first mid pivot = data[first]; data[first] = data[last]; data[last] = data[mid]; data[mid] = data[first+1]; data[first+1] = pivot; } else { // first last mid pivot = data[last]; data[last] = data[mid]; data[mid] = data[first+1]; data[first+1] = pivot; } else { // first mid last data[mid] = data[first+1]; data[first+1] = pivot; } int iLo = first + 2, iHi = last-1; //lowest, highest untested indices while (iLo <= iHi) { while (data[iHi] > pivot) iHi--; while (data[iLo] < pivot) iLo++; if (iLo <= iHi) { int temp = data[iLo]; data[iLo] = data[iHi]; data[iHi] = temp; iHi--; iLo++; } } int iPivot = iLo-1; // place of last smaller value data[first+1] = data[iPivot]; // swap with pivot data[iPivot] = pivot; return iPivot; } public static void insertionsort(int[ ] data, int start, int end) { for (int next = start + 1; next <= end; next++) { if (data[next-1] > data[next]) { int val = data[next]; int gap = next-1; data[next] = data[gap]; while (gap > start && data[gap-1] > val) { data[gap] = data[gap-1]; gap--; } data[gap] = val; // next line initially included since insertion sort can hide bad qsort // if (gap + MAX_INSERTION_SORT < next) System.err.println("Bad qsort"); } // end: if not already in place } // end: for each element to be inserted } }