JanR at 10:32, 20 October 2014

2014-10-20T10:32:23Z

← Older revision		Revision as of 10:32, 20 October 2014
Line 4:		Line 4:
	# an arc weight <math> l(a) \in \mathbb{R}</math> for each arc <math>a \in 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>		# a '''root node''' <math> s \in V </math>


	== Output ==		== Output ==
Line 17:		Line 16:
	== Known algorithms ==		== Known algorithms ==
	[[Dijkstra]]		[[Dijkstra]]


	== Known variants ==		== Known variants ==

JanR at 10:30, 20 October 2014

2014-10-20T10:30:15Z

← Older revision		Revision as of 10:30, 20 October 2014
Line 7:		Line 7:

	== Output ==		== Output ==
	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>		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>

	== Objective ==		== Objective ==
	N/A		N/A



	== Complexity ==		== Complexity ==
	Polynomial		Polynomial

	== Known algorithms ==		== Known algorithms ==

JanR: Replaced content with " == Input == # A directed graph $G=(V,A)$ # an arc weight $l(a) \in \mathbb{R}$ for each arc $a \in A$ # a '''root node''' $s \in V..."$

2014-10-20T10:28:39Z

Replaced content with " == 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..."

Show changes

JanR: Created page with "Category:Sorting Algorithms Category:Divide and Conquer

2014-10-20T10:04:31Z

Created page with "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:1e..."

New page
[[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>

<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>
</div>

== 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: ===
# 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 ==

=== Statement: ===
In the worst case, the complexity is <math>\Theta(n^2)</math>.

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.

Single source shortest paths - Revision history

JanR at 10:32, 20 October 2014

JanR at 10:30, 20 October 2014

JanR: Replaced content with " == Input == # A directed graph G=(V,A) # an arc weight l(a) \in \mathbb{R} for each arc a \in A # a '''root node''' s \in V..."

JanR: Replaced content with " == Input == # A directed graph $G=(V,A)$ # an arc weight $l(a) \in \mathbb{R}$ for each arc $a \in A$ # a '''root node''' $s \in V..."$