Algorithms in a Nutshell

(^82) | Chapter 4: Sorting Algorithms
Solution
The QUICKSORTimplementation shown in Example 4-7 can be defined in terms
of the functions already presented in “Median Sort.” We use a standard optimiza-
tion technique that uses INSERTIONSORTwhen the size of the subarray to be
sorted falls below a predetermined minimum size.
The choice ofpivotis made by the external methodselectPivotIndex(ar, left,
right), which provides the array element for which to partition.
Consequences
Surprisingly, the random algorithm for selecting a pivot enables QUICKSORTto
provide an average-case performance that usually outperforms other sorting algo-
rithms. In addition, there are numerous enhancements and optimizations
researched for QUICKSORTthat have wrought the most efficiency out of any
sorting algorithm. The various options are discussed in detail later, in the
upcoming “Variations” section.
Example 4-7. Quicksort implementation in C
/**

• Sort array ar[left,right] using Quicksort method.


• The comparison function, cmp, is needed to properly compare elements.
  */
  void do_qsort (void ar, int(cmp)(const void ,const void ),
  int left, int right) {
  int pivotIndex;
  if (right <= left) { return; }
  / partition */
  pivotIndex = selectPivotIndex (ar, left, right);
  pivotIndex = partition (ar, cmp, left, right, pivotIndex);
  if (pivotIndex-1-left <= minSize) {
  insertion (ar, cmp, left, pivotIndex-1);
  } else {
  do_qsort (ar, cmp, left, pivotIndex-1);
  }
  if (right-pivotIndex-1 <= minSize) {
  insertion (ar, cmp, pivotIndex+1, right);
  } else {
  do_qsort (ar, cmp, pivotIndex+1, right);
  }
  }
  /* Qsort straight /
  void sortPointers (void vals, int total_elems,
  int(cmp)(const void ,const void *)) {
  do_qsort (vals, cmp, 0, total_elems-1);
  }
  Algorithms in a Nutshell
  Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
  9780596516246 Publisher: O'Reilly Media, Inc.
  Prepared for Ming Yi, Safari ID: [email protected]
  Licensed by Ming Yi
  Print Publication Date: 2008/10/21 User number: 594243
  © 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use