Source of quicksort.cpp

Structures and functions

  1: //  Created by Frank M. Carrano and Tim Henry.
  2: //  Copyright (c) 2013 __Pearson Education__. All rights reserved.

  4: // Listing 11-5.

  6: template<class ItemType>

  8: /** Sorts an array into ascending order. Uses the quick sort with
  9:  median-of-three pivot selection for arrays of at least MIN_SIZE
 10:  entries, and uses the insertion sort for other arrays.
 11:  @pre  theArray[first..last] is an array.
 12:  @post  theArray[first..last] is sorted.
 13:  @param theArray  The given array.
 14:  @param first  The first element to consider in theArray.
 15:  @param last  The last element to consider in theArray. */
 16: void quickSort(ItemType theArray[], int first, int last)
 17: {
 18:    if (last - first + 1 < MIN_SIZE)
 19:    {
 20:       insertionSort(theArray, first, last);
 21:    }
 22:    else
 23:    {
 24:       // Create the partition: S1 | Pivot | S2
 25:       int pivotIndex = partition(theArray, first, last);
 26:       
 27:       // Sort subarrays S1 and S2
 28:       quickSort(theArray, first, pivotIndex - 1);
 29:       quickSort(theArray, pivotIndex + 1, last);
 30:    }  // end if
 31: }  // end quickSort