Algorithms in a Nutshell

(^78) | Chapter 4: Sorting Algorithms
Quicksort
If we reflect on the performance of MEDIANSORT, we see that a random choice of
pivotIndexstill enables the average-case performance ofselectKthto operate in
linear time. Is it possible to simplify the algorithm without incurring an extra
performance penalty? Would the simpler implementation perhaps be faster in
some situations? The QUICKSORTalgorithm, first introduced by C.A.R. Hoare, is
indeed simpler than MEDIANSORT, although it uses many of the same concepts,
which is why we introduced MEDIANSORTfirst.
} else {
return medianOfMedians (ar, cmp, left+span/2, s-1, span);
}
}
/**

• Linear worst-case time algorithm to find median in ar[left,right]. The


• comparison function, cmp, is needed to compare elements.
  */
  int selectMedian (void *ar, int(cmp)(const void ,const void ),
  int left, int right) {
  int k = (right-left+1)/2;
  while (k > 0) {
  / Choose index around which to partition. /
  int idx = medianOfMedians (ar, cmp, left, right, 1);
  /**


• Partition input array around the median of medians x. If kth


• largest is found, return absolute index; otherwise narrow to


• find kth smallest in A[left,pivotIndex-1] or (k-p)-th


• in A[pivotIndex+1,right].
  /
  int pivotIndex = partition (ar, cmp, left, right, idx);
  / Note that k is in range 0 <=k <= right-left while the returned
  pivotIndex is in range left <= pivotIndex <= right. /
  int p = left+k;
  if (p == pivotIndex) {
  return pivotIndex;
  } else if (p < pivotIndex) {
  right = pivotIndex-1;
  } else {
  k = k - (pivotIndex-left+1);
  left = pivotIndex+1;
  }
  }
  / If we get here, then left=right, so just return one as median. */
  return left;
  }
  Example 4-6. Blum-Floyd-Pratt-Rivest-Tarjan implementation in C (continued)
  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