Algorithms in a Nutshell

Quicksort | 83

Sorting

Algorithms

Analysis

In the ideal case,partitiondivides the original array in half; if this behavior is

consistent for each recursion, then the resulting behavior produces the same

results as MEDIANSORTwithout incurring an additional performance penalty.

Let’s definet(n) to be the time to perform QUICKSORTon an array ofnelements.

Because QUICKSORT is recursive, we can state that:

t(n) = 2*t(n/2)+O(n)

where O(n) captures the linear work needed to partition the subarrays. As shown

in Chapter 2, algorithms that behave according to thist(n) definition have perfor-

mance of O(nlogn). QUICKSORTis empirically faster than MEDIANSORTsimply

because the constants abstracted by O(n) are smaller. There is less overhead for

QUICKSORTbecause it does not have to find the median element when

constructing the subproblems; indeed, even a randomly selectedpivotis shown, in

practice, to suffice, and this requires only a single execution ofpartitionfor each

recursive invocation of QUICKSORT(whereas MEDIANSORTmight need to recur-

sively invokepartitionmultiple times when it seeks to compute the median

element).

In the worst case, the largest or the smallest item is picked as the pivot. When this

happens, QUICKSORTmakes a pass over all elements in the array (in linear time)

to sort just a single item in the array. In the worst case, this process is repeated

n–1 times, resulting in O(n^2 ) worst-case behavior.

Variations

QUICKSORTis the sorting method of choice on most systems. On Unix- and

Linux-based systems, there is a built-in library function calledqsort.*Often, the

operating system uses optimized versions of the default QUICKSORTalgorithm.

Two of the commonly cited sources for optimizations are by Sedgewick (1978)

and Bentley and McIlroy (1993).

Various optimizations include:

• Create a stack that stores the subtasks to be processed to eliminate recursion.


• Choose the pivot based upon median-of-three.


• Set minimum partition size to use INSERTIONSORTinstead (which varies by
  implementation and machine architecture; for example, on the Sun4 architec-
  ture the minimum value is set to 4 based on empirical evaluation).


• When processing subarrays, push larger partition onto the stack first to mini-
  mize the total size of the stack by ensuring that the smaller problem is
  worked on first.
  It is important to recognize that none of these optimizations will eliminate the
  O(n^2 ) worst-case behavior of QUICKSORT. The only way to ensure an O(nlogn)
  worst-case performance is to use a selection algorithm such as BFPRT, described

* It is instructive that some versions of the Linux operating system implementqsortusing HEAP

SORT, discussed in the upcoming section “Heap Sort.”

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