Algorithms in a Nutshell

(^84) | Chapter 4: Sorting Algorithms
in Example 4-6, although this will result in a degraded average-case performance.
If a true O(nlogn) worst-case performance is required, consider using HEAP
SORT, discussed in the next section.
Picking a pivot
Selecting the pivot element from a subarrayA[left,left+n) must be an efficient
operation; it shouldn’t require checking allnelements of the subarray. Some alter-
natives are:

• Select first or last:A[left] orA[left+n–1]


• Select random element inA[left,left+n–1]


• Select median-of-k: the middle value ofk random elements inA[left,left+n–1]
  Often one choosesk=3, and, not surprisingly, this variation is known as median-
  of-three. Sedgewick reports that this approach returns an improvement of 5%, but
  note that some arrangements of data will force even this alternative into subpar
  performance (Musser, 1997). A median-of-five pivot selection has also been used.
  Performing further computation to identify the proper pivot is rarely able to
  provide beneficial results because of the incurred costs, which make the algo-
  rithm approach MEDIANSORTin performance (indeed, MEDIANSORTtakes this
  variation to the extreme by selecting the median-of-n).

Processing the partition

In thepartitionmethod shown in Example 4-3, elements less than or equal to the

selected pivot are inserted toward the front of the subarray. This approach might

skew the size of the subarrays for the recursive step if the selected pivot has many

duplicate elements in the array. One way to reduce the imbalance is to place

elements equal to the pivot alternatively in the first subarray and second subarray.

Processing subarrays

QUICKSORTusually yields two recursive invocations of QUICKSORTon smaller

subarrays. While processing one, the activation record of the other is pushed onto

the execution stack. If the larger subarray is processed first, it is possible to have a

linear number of activation records on the stack at the same time (although

modern compilers may eliminate this observed overhead). To minimize the

possible depth of the stack, process the smaller subarray first.

If the depth of the system stack is a foreseeable issue, then perhaps QUICKSORTis

not appropriate for your application. One way to break the impasse is to use a

stack data structure to store the set of subproblems to be solved, rather than

relying on recursion.

Using simpler insertion technique for small subarrays

On small arrays, INSERTIONSORTis faster than QUICKSORT, but even when

used on large arrays, QUICKSORTultimately decomposes the problem to require

numerous small subarrays to be sorted. One commonly used technique to

improve the recursive performance QUICKSORTis to invoke QUICKSORTfor large

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

Licensed by

Ming Yi