// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. // Quicksort implementation and timing test driver // Basic Quicksort version #include "book.h" // Include comparator functions #include "compare.h" // Simple findpivot: Pick middle value in array template inline int findpivot(E A[], int i, int j) { return (i+j)/2; } // Partition the array template inline int partition(E A[], int l, int r, E& pivot) { do { // Move the bounds inward until they meet while (Comp::prior(A[++l], pivot)); // Move l right and while ((l < r) && Comp::prior(pivot, A[--r])); // r left swap(A, l, r); // Swap out-of-place values } while (l < r); // Stop when they cross return l; // Return first position in right partition } // qsort core function: Basic qsort template void qsort(E A[], int i, int j) { // Quicksort if (j <= i) return; // Don't sort 0 or 1 element int pivotindex = findpivot(A, i, j); swap(A, pivotindex, j); // Put pivot at end // k will be the first position in the right subarray int k = partition(A, i-1, j, A[j]); swap(A, k, j); // Put pivot in place qsort(A, i, k-1); qsort(A, k+1, j); } template void sort(E* array, int n) { qsort(array, 0, n-1); } #include "sortmain.cpp" int main(int argc, char** argv) { return sortmain(argc, argv); }