Quicksort

From Algowiki
Jump to: navigation, search

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.

Remark: For a particular recursive call [math]C[/math], we may, for example, choose the height of the recursion subtree with root [math]C[/math] as the induction parameter. For conciseness, the induction parameter is omitted in the following.

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

Implementation:

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

Correctness:

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

  1. If [math]x,y \in S_1'[/math] or [math]x,y \in S_3'[/math], [math]x \leq y[/math] resultes from the induction hypothesis.
  2. On the other hand, if [math]x,y \in S_2[/math]. It is [math]x = y = p[/math], which trivially implies [math]x \leq y[/math].
  3. Finally, for the following cases, [math]x \leq y[/math] is implied by the specific way of partitioning [math]S[/math] into [math]S_1'[/math], [math]S_2[/math] and [math]S_3'[/math]:
    1. [math]x \in S_1'[/math] and [math]y \in S_2[/math]
    2. [math]x \in S_2[/math] and [math]y \in S_3'[/math]
    3. [math]x \in S_1'[/math] and [math]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]\Theta(T\cdot n^2)[/math], where [math]T[/math] is the complexity of the comparison.

If the pivoting rule ensures for some [math]\alpha \lt 1[/math] that the lengths of [math]S_1[/math] and [math]S_3[/math] are at most [math]\alpha[/math] times the size of [math]S[/math], then it is even [math]\Theta(T\cdot 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]\Theta(T\cdot n \log n)[/math].

Proof:

First note that the complexity for a single recursive call on [math]S[/math] (excluding the complexity for the recursive descents on [math]S_1[/math] and [math]S_3[/math]) is in [math]\Theta(T\cdot|S|)[/math]. On each recursive level, all calls are on distinct subsets of [math]S[/math]. Therefore, the number of recursive calls with non-empty sequences on one recursive level is in [math]\Theta(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]O(n)[/math] as well. In summary, the total complexity on a recursive level is [math]O(T\cdot 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]O(n)[/math]. On the other hand, [math]\Omega(n)[/math] in the very worst case is obvious. This gives the claimed [math]\Theta(T\cdot n^2)[/math] in the worst case.

Next assume there is a fixed [math]\alpha \lt 1[/math] such that [math]|S_1| \leq \alpha \cdot|S|[/math] and [math]|S_3| \leq \alpha \cdot|S|[/math] is guaranteed in each recursive call. Then the length of any sequence on recursive level [math]\#i[/math] is at most [math]\alpha ^ i \cdot |S|[/math]. Therefore, the maximal recursive depth is [math]\lceil \log_{a^{-1}}(n)\rceil[/math]. Since [math]\alpha^{-1} \gt 1[/math], the total complexity is in [math]O(T\cdot 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]x,y \in S[/math] are compared at most once throughout the entire algorithm if, and only if, [math]x[/math] or [math]y[/math] is chosen as the pivot value for a subsequence to which both elements belong. For [math]x,y \in S[/math], let [math]Pr(x,y)[/math] denote the probability that [math]x[/math] and [math]y[/math] are indeed compared. Since comparison events are distinct and [math]Pr(x,y )\in \{0,1\}[/math] for all [math]x,y \in S[/math], the expected number of comparisons is

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


Let [math]n := |S|[/math], and for [math]i,j \in \{1,\dots,n\}[/math], let [math]Pr(i,j)[/math] denote the probability that the [math]i[/math]-th and the [math]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]\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]i,j \in \{1,\dots,n\}[/math], [math]i \lt j[/math], let [math] S_{ij}[/math] denote the subsequence of the eventual sorted sequence that starts with [math]i[/math] and ends with [math]j[/math]. The elements [math]\#i[/math] and [math]\#j[/math] are compared if, and only if, [math]\#i[/math] or [math]\#j[/math] is the very first element of [math]S_{ij}[/math] to be chosen as a pivot. The probability of this event is [math]\frac{2}{|S_{ij}|} = \frac{2}{j - i + 1}[/math], so we obtain

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


Substituting [math]k := j-i[/math], this gives

[math]\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]\sum_{k=1}^n \frac{1}{k+1} \leq 2(n-1)[/math].


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


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

Further information

If [math]S[/math] is an array, [math]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]S_1[/math] and [math]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.