Quicksort

Quick Sort

whatever

Openlearnware

General information

Algorithmic problem: Sorting based on pairwise comparison

Type of algorithm: recursion

Abstract view

Invariant: After a recursive call, the input sequence of this recursive call is sorted.

Variant: In each recursive call, the sequence of the callee is strictly shorter than that of the caller.

Break condition: The sequence is empty or a singleton.

Induction basis

Abstract view: Nothing to do on an empty sequence or a singleton.

Implementation: Ditto.

Proof: Empty sequences and singletons are trivially sorted.

Induction step

Abstract view:

1. Choose a pivot value [math]\displaystyle{ p \in [min\{x|x \in S\},\dots,max\{x|x \in S\}] }[/math] (note that [math]\displaystyle{ p }[/math] is not required to be an element of [math]\displaystyle{ S }[/math].
2. Partition [math]\displaystyle{ S }[/math] into sequences, [math]\displaystyle{ S_1 }[/math], [math]\displaystyle{ S_2 }[/math] and [math]\displaystyle{ S_3 }[/math], such that [math]\displaystyle{ x \lt p }[/math] for all [math]\displaystyle{ x \in S_1 }[/math], [math]\displaystyle{ x = p }[/math] for all [math]\displaystyle{ x \in S_2 }[/math], and [math]\displaystyle{ x \gt p }[/math] for all [math]\displaystyle{ x \in S_3 }[/math].
3. Sort [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_3 }[/math] recursively.
4. The concatenation of all three lists, [math]\displaystyle{ S_1 + S_2 + S_3 }[/math], is the result of the algorithm.

Implementation:

1. Chose [math]\displaystyle{ p \in [min\{x|x \in S\},\dots,max\{x|x \in S\}] }[/math] according to some pivoting rule.
2. [math]\displaystyle{ S_1 := S_2 := S_3 := \emptyset }[/math].
3. For all [math]\displaystyle{ x \in S }[/math], append [math]\displaystyle{ x }[/math] to
   1. [math]\displaystyle{ S_1 }[/math] if [math]\displaystyle{ x \lt p }[/math],
   2. [math]\displaystyle{ S_2 }[/math] if [math]\displaystyle{ x = p }[/math],
   3. [math]\displaystyle{ S_3 }[/math] if [math]\displaystyle{ x \gt p }[/math].
4. Call Quicksort on [math]\displaystyle{ S_1 }[/math] giving [math]\displaystyle{ S_1' }[/math]
5. Call Quicksort on [math]\displaystyle{ S_3 }[/math] giving [math]\displaystyle{ S_3' }[/math]
6. Return [math]\displaystyle{ S_1' + S_2' + S_3' }[/math].

Correctness:

By induction hypothesis, [math]\displaystyle{ S_1' }[/math] and [math]\displaystyle{ S_3' }[/math] are sorted permutations of [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_3 }[/math], respectively. In particular [math]\displaystyle{ S_1' \| S_2 \| S_3' }[/math] is a permutation of [math]\displaystyle{ S }[/math]. To see that this permutation is sorted, let [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] be two members of [math]\displaystyle{ S }[/math] such that [math]\displaystyle{ y }[/math] immediately succeeds [math]\displaystyle{ x }[/math] in the resulting sequence [math]\displaystyle{ S_1' \| S_2 \| S_3' }[/math]. We have to show [math]\displaystyle{ x \leq y }[/math].

1. If [math]\displaystyle{ x,y \in S_1' }[/math] or [math]\displaystyle{ x,y \in S_3' }[/math], [math]\displaystyle{ x \leq y }[/math] resultes from the induction hypothesis.
2. On the other hand, if [math]\displaystyle{ x,y \in S_2 }[/math]. It is [math]\displaystyle{ x = y = p }[/math], which trivially implies [math]\displaystyle{ x \leq y }[/math]
3. Finally, for following cases, [math]\displaystyle{ x \leq y }[/math] is implied by the specific way of partitioning [math]\displaystyle{ S }[/math] into [math]\displaystyle{ S_1' }[/math], [math]\displaystyle{ S_2 }[/math] and [math]\displaystyle{ S_3' }[/math]:
   1. [math]\displaystyle{ x \in S_1' }[/math] and [math]\displaystyle{ y \in S_2 }[/math]
   2. [math]\displaystyle{ x \in S_2 }[/math] and [math]\displaystyle{ y \in S_3' }[/math]
   3. [math]\displaystyle{ x \in S_1' }[/math] and [math]\displaystyle{ y \in S_3' }[/math]

Obviously, this case distinction covers all potential cases, so the claim is proved.

Complexity

Statement:

recursion depth of quick sort : [A] best case, [B] avg. case, [C] worst case

In the worst case, the complexity is [math]\displaystyle{ \Theta(n^2) }[/math].

If the pivot rule ensures for some [math]\displaystyle{ \alpha \lt 1 }[/math] that the lengths of [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_3 }[/math] are at most [math]\displaystyle{ \alpha }[/math] times the size of [math]\displaystyle{ S }[/math], then it is even [math]\displaystyle{ O(n \log n) }[/math] in the worst case.

If each pivot value is chosen uniformly randomly from members of the respective sequence and if all selections of pivot values are stochastically independent, the average-case complexity is [math]\displaystyle{ O(n \log n) }[/math].

Proof:

First note that the complexity for a single recursive call on [math]\displaystyle{ S }[/math] (disregarding the complexity for the recursive descents on [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_3 }[/math] is in [math]\displaystyle{ O(|S|) }[/math]. On each recursive level, all calls are on distinct subsets of [math]\displaystyle{ S }[/math]. Therefore, the number of recursive calls with non-empty sequences on one recursive level is in [math]\displaystyle{ O(n) }[/math]. The number of calls with empty sequences on one level is at most twice the total number of calls with non-empty sequences on the previous level. Hence, the number of calls with empty sequences on one recursive level is in [math]\displaystyle{ O(n) }[/math] as well. In summary, the total complexity on a recursive level is [math]\displaystyle{ O(n) }[/math]. So, for the total complexity, it remains to estimate the number of recursive levels.

Now consider the first statement. The recursion variant implies that the deepest recursive level is [math]\displaystyle{ O(n) }[/math]. This gives the claimed [math]\displaystyle{ O(n^2) }[/math] in the worst case.

Next assume there is a fixed [math]\displaystyle{ \alpha \lt 1 }[/math] such that [math]\displaystyle{ |S_1| \leq \alpha \cdot|S| }[/math] and [math]\displaystyle{ |S_3| \leq \alpha \cdot|S| }[/math] is guaranteed in each recursive call. Then the length of any sequence on recursive level [math]\displaystyle{ \#i }[/math] is at most [math]\displaystyle{ \alpha ^ i \cdot |S| }[/math]. Therefore, the maximal recursive depth is [math]\displaystyle{ \lceil \log_{a-1}(n)\rceil }[/math]. Since [math]\displaystyle{ \alpha^{-1} \gt 1 }[/math], the total complexity is in [math]\displaystyle{ O(n \log n) }[/math] in the worst case.

For the last statement, the average-case analysis, first note that the number of comparisons alone has the same asymptotic complexity as the algorithm as a whole. Next note that any [math]\displaystyle{ x,y \in S }[/math] are compared at most once throughout the entire algorithm if, and only if, [math]\displaystyle{ x }[/math] or [math]\displaystyle{ y }[/math] is chosen as the pivot value for a subsequence to which both elements belong. For [math]\displaystyle{ x,y \in S }[/math], let [math]\displaystyle{ Pr(x,y) }[/math] denote the probability that [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] are indeed compared. Since comparison events are distinct and [math]\displaystyle{ Pr(x,y )\in \{0,1\} }[/math] for all [math]\displaystyle{ x,y \in S }[/math], the expected number of comparisons is

[math]\displaystyle{ \sum_{x,y \in S, x \neq y} Pr(x,y) }[/math]

Let [math]\displaystyle{ n := |S| }[/math], and for [math]\displaystyle{ i,j \in \{1,\dots,n\} }[/math], let [math]\displaystyle{ Pr(i,j) }[/math] denote the probability that the [math]\displaystyle{ i }[/math]-th and the [math]\displaystyle{ j }[/math]-th elemet of the eventual sorted sequence are compared throughout the algorithm. Using this notation, we may rewrite the above summation as follows:

[math]\displaystyle{ \sum_{x,y \in S, x \neq y} Pr(x,y) = \sum_{i=1}^{n-1} \sum_{j = i+1}^{n} Pr(i,j) }[/math].

For [math]\displaystyle{ i,j \in \{1,\dots,n\} }[/math], [math]\displaystyle{ i \lt j }[/math], let [math]\displaystyle{ S_{ij} }[/math] denote the subsequence of the eventual sorted sequence that starts with [math]\displaystyle{ i }[/math] and ends with [math]\displaystyle{ j }[/math]. The elements [math]\displaystyle{ \#i }[/math] and [math]\displaystyle{ \#j }[/math] are compared if, and only if, [math]\displaystyle{ \#i }[/math] or [math]\displaystyle{ \#j }[/math] is the very first element of [math]\displaystyle{ S_{ij} }[/math] to be chosen as a pivot. The probability of this event is [math]\displaystyle{ \frac{2}{|S_{ij}|} = \frac{2}{j - i + 1} }[/math], so we obtain

[math]\displaystyle{ \sum_{i=1}^{n-1} \sum_{j = i+1}^{n} \frac{2}{j-i+1} }[/math].

Substituting [math]\displaystyle{ k := j-i }[/math], this gives

[math]\displaystyle{ \sum_{i=1}^{n-1} \sum_{j = i+1}^{n} \frac{2}{j-i+1} = \sum_{i=1}^{n-1} \sum_{k=1}^{n} \frac{2}{k+1} \leq 2(n - 1) }[/math].

[math]\displaystyle{ \sum_{k=1}^n \frac{1}{k+1} \leq 2(n-1) }[/math].

[math]\displaystyle{ \sum_{k+1}^n \frac{1}{k} }[/math].

The asymptotic behavior of the harmonic series is [math]\displaystyle{ \Theta(\log n) }[/math], so the last expression is [math]\displaystyle{ \Theta(n \log n) }[/math].

Further information

If [math]\displaystyle{ S }[/math] is an array, [math]\displaystyle{ S }[/math] cannot be decomposed into subsequences. We would liko to avoid the need for additional arrays and copy operations. Instead, the array should be sorted in-place, that is, by swap operations on pairs of elements. The auxiliary procedure, Pivot partitioning by scanning, is designed exactly for that: it permutes the array such that each of [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_2 }[/math] is a subarray. Then each recursive call of Quicksort operates on a subarray of the input array, which is specified by two index pointers.