|
|
| (2 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| [[Category:Sorting Algorithms]]
| |
| [[Category:Divide and Conquer]]
| |
| <div class="plainlinks" style="float:right;margin:0 0 5px 5px; border:1px solid #AAAAAA; width:auto; padding:1em; margin: 0px 0px 1em 1em;">
| |
| <div style="font-size: 1.8em;font-weight:bold;text-align: center;margin:0.2em 0 1em 0">Quick Sort</div>
| |
|
| |
|
| <div style="font-size: 1.2em; margin:.5em 0 1em 0; text-align:center">whatever</div> | | == Input == |
| | # A directed graph <math>G=(V,A)</math> |
| | # an arc weight <math> l(a) \in \mathbb{R}</math> for each arc <math>a \in A</math> |
| | # a '''root node''' <math> s \in V </math> |
|
| |
|
| <div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/quick-sort-1945 Openlearnware]</div> | | == Output == |
| </div> | | For each <math>v \in V</math>, a real value <math>\delta (v)</math>, the '''length''' of a shortest <math>(s,v)</math>-path in <math>G</math> subject to <math>l</math> |
|
| |
|
| == General information == | | == Objective == |
| '''Algorithmic problem:''' [[Sorting based on pairwise comparison]]
| | N/A |
| | |
| '''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: ===
| |
| # 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>.
| |
| # Partition <math>S</math> into sequences, <math>S_1</math>, <math>S_2</math> and <math>S_3</math>, such that <math>x < 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 > p</math> for all <math>x \in S_3</math>.
| |
| # Sort <math>S_1</math> and <math>S_3</math> recursively.
| |
| # The concatenation of all three lists, <math>S_1 \| S_2 \| S_3</math>, is the result of the algorithm.
| |
| | |
| === Implementation: ===
| |
| | |
| # Chose <math>p \in [min\{x|x \in S\},\dots,max\{x|x \in S\}]</math> according to some pivoting rule.
| |
| # <math>S_1 := S_2 := S_3 := \emptyset</math>.
| |
| # For all <math>x \in S</math>, append <math>x</math> to
| |
| ## <math>S_1</math> if <math>x < p</math>,
| |
| ## <math>S_2</math> if <math>x = p</math>,
| |
| ## <math>S_3</math> if <math>x > p</math>.
| |
| # Call Quicksort on <math>S_1</math> giving <math>S_1'</math>
| |
| # Call Quicksort on <math>S_3</math> giving <math>S_3'</math>
| |
| # 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>.
| |
| # 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.
| |
| # 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>
| |
| # Finally, for 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>:
| |
| ## <math>x \in S_1'</math> and <math>y \in S_2</math>
| |
| ## <math>x \in S_2</math> and <math>y \in S_3'</math>
| |
| ## <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 == | | == Complexity == |
| | Polynomial |
|
| |
|
| === Statement: === | | == Known algorithms == |
| In the worst case, the complexity is <math>\Theta(n^2)</math>.
| | [[Dijkstra]] |
| | |
| If the pivot rule ensures for some <math>\alpha < 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>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>O(n \log n)</math>.
| |
| | |
| === Proof: ===
| |
| First note that the complexity for a single recursive call on <math>S</math> (disregarding the complexity for the recursive descents on <math>S_1</math> and <math>S_3</math> is in <math>O(|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>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>O(n)</math> as well. In summary, the total complexity on a recursive level is <math>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>O(n)</math>. This gives the claimed <math>O(n^2)</math> in the worst case.
| |
| | |
| | |
| | |
| Next assume there is a fixed <math>\alpha < 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} > 1</math>, the total complexity is in <math>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>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 value|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 < 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 [http://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#Rate_of_divergence asymptotic behavior] of the [http://en.wikipedia.org/wiki/Harmonic_series_(mathematics) harmonic series] is <math>\Theta(\log n)</math>, so the last expression is <math>\Theta(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.
| | == Known variants == |