Data Abstraction and Problem Solving with C++ Walls and Mirrors by Frank M. Carrano
Text Home Text Errata	quicksort.cpp File Reference Detailed Description Implementation of the quick sort algorithm. Date: 29 May 2006 Chapter: Chapter 9 Page: Page 483 Version: 5.0 Definition in file quicksort.cpp. Go to the source code of this file. Functions void  choosePivot (DataType theArray[], int first, int last) void  partition (DataType theArray[], int first, int last, int &pivotIndex) void  quicksort (DataType theArray[], int first, int last) Function Documentation void choosePivot (  DataType  theArray[], int  first, int  last )    Chooses a pivot for quicksort's partition algorithm and swaps it with the first item in an array. Precondition: theArray[first..last] is an array; first <= last. Postcondition: theArray[first] is the pivot. Parameters: theArray  The given array. first  The first element to consider in theArray. last  The last element to consider in theArray. Referenced by partition(). void partition (  DataType  theArray[], int  first, int  last, int &  pivotIndex )    Partitions an array for quicksort. Precondition: theArray[first..last] is an array; first <= last. Postcondition: Partitions theArray[first..last] such that: S1 = theArray[first..pivotIndex-1] < pivot theArray[pivotIndex] == pivot S2 = theArray[pivotIndex+1..last] >= pivot Parameters: theArray  The given array. first  The first element to consider in theArray. last  The last element to consider in theArray. pivotIndex  The index of the pivot after partitioning. Definition at line 35 of file quicksort.cpp. References choosePivot(), and swap(). Referenced by quicksort(). void quicksort (  DataType  theArray[], int  first, int  last )    Sorts the items in an array into ascending order. Precondition: theArray[first..last] is an array. Postcondition: theArray[first..last] is sorted. Parameters: theArray  The given array. first  The first element to consider in theArray. last  The last element to consider in theArray. Definition at line 73 of file quicksort.cpp. References partition().

---