1: // Created by Frank M. Carrano and Timothy M. Henry.
2: // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
4: // Listing 11-5.
6: /** Sorts an array into ascending order. Uses the quick sort with
7: median-of-three pivot selection for arrays of at least MIN_SIZE
8: entries, and uses the insertion sort for other arrays.
9: @pre theArray[first..last] is an array.
10: @post theArray[first..last] is sorted.
11: @param theArray The given array.
12: @param first The index of the first element to consider in theArray.
13: @param last The index of the last element to consider in theArray. */
14: template <class ItemType>
15: void quickSort(ItemType theArray[], int first, int last)
16: {
17: if ((last − first + 1) < MIN_SIZE)
18: {
19: insertionSort(theArray, first, last);
20: }
21: else
22: {
23: // Create the partition: S1 | Pivot | S2
24: int pivotIndex = partition(theArray, first, last);
25:
26: // Sort subarrays S1 and S2
27: quickSort(theArray, first, pivotIndex − 1);
28: quickSort(theArray, pivotIndex + 1, last);
29: } // end if
30: } // end quickSort