PlanetMath: quicksort

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (22)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

quicksort

(Definition)

Quicksort is a divide-and-conquer algorithm for sorting in the comparison model. Its expected running time is $O(n\lg n)$ for sorting values.

Algorithm

Quicksort can be implemented recursively, as follows:

Algorithm QUICKSORT()
Input: A list of elements
Output: The list in sorted order
if then
$\textstyle \parbox{\textwidth}{ $p \gets \mbox{ random element of } L$\ $A \g... ...sort(A)$\ $S_C \gets Quicksort(C)$\ {\bf return} $Concatenate(S_A,B,S_C)$ }$
else
$\textstyle \parbox{\textwidth}{{\bf return} $L$}$

Analysis

The behavior of quicksort can be analyzed by considering the computation as a binary tree. Each node of the tree corresponds to one recursive call to the quicksort procedure.

Consider the initial input to the algorithm, some list . Call the Sorted list with th and th elements and These two elements will be compared with some probability $p_{ij}$ . This probability can be determined by considering two preconditions on and being compared:

or must be chosen as a pivot , since comparisons only occur against the pivot.
No element between and can have already been chosen as a pivot before or is chosen. Otherwise, would be separated into different sublists in the recursion.

The probability of any particular element being chosen as the pivot is uniform. Therefore, the chance that or is chosen as the pivot before any element between them is . This is precisely $p_{ij}.$

The expected number of comparisons is just the summation over all possible comparisons of the probability of that particular comparison occurring. By linearity of expectation, no independence assumptions are necessary. The expected number of comparisons is therefore

$\displaystyle \sum_{i=1}^{n}\sum_{j>i}^{n}p_{ij}$	$\displaystyle =$	$\displaystyle \sum_{i=1}^{n}\sum_{j>i}^{n}\frac{2}{j-i+1}$	(1)
	$\displaystyle =$	$\displaystyle \sum_{i=1}^{n}\sum_{k=2}^{n-i+1}\frac{2}{k}$	(2)
	$\displaystyle \le$	$\displaystyle 2\sum_{i=1}^{n}\sum_{k=1}^{n}\frac{1}{k}$	(3)
	$\displaystyle =$	$\displaystyle 2nH_n = O(n\lg n),$	(4)

where is the th Harmonic number.

The worst case behavior is $\Theta(n^2)$ , but this almost never occurs (with high probability it does not occur) with random pivots.

"quicksort" is owned by thouis.

(view preamble | get metadata)