Algowiki - User contributions [en]

Bellman-Ford

2014-10-21T17:51:14Z

Bencina: Struktur angepasst

__NOTOC__
[[Category:Checkup]]
[[Category:Algorithm]]
[[Category:Main Algorithm]]
==General information==
'''Algorithmic problem:''' [[All pairs shortest paths]]

'''Prerequisites:'''

'''Type of algorithm:''' loop

'''Auxiliary data:'''
# A [[Paths|distance-valued]] <math>(n \times n)</math> matrix <math>M</math>, where <math>n=|V|</math>. The eventual contents of <math>M</math> will be returned as the result of the algorithm.
# A [[Paths|distance-valued]] <math>(n \times n)</math> matrix <math>L</math>, where <math>n=|V|</math>. This matrix represents the graph and the arc lengths and will not be changed throughout the algorithm. It is <math>L=M^1</math> in the terminology of Section "Powers of distance matrices" on [[Paths#Powers of distance matrices|this]] page.

==Abstract view==
'''Invariant:''' After <math>i \ge 0</math> iterations, <math>M^i (v,w)</math> contains the length of a shortest <math>(v,w)</math>-path with at most <math>i+1</math> arcs (for all <math>v,w \in V</math>).

'''Variant:''' <math>i</math> increases by 1.

'''Break condition:''' <math>i=n-1</math>.

==Induction basis==
'''Abstract view:''' For all <math>v,w \in V</math>, we set
# <math>M^0 (v,v):= L(v,v) := 0</math>;
# <math>M^0 (v,w):= L(v,w) := \ell (v,w)</math> if <math>(v,w)\in A</math>;
# <math>M^0 (v,w):= L(v,w) := +\infty</math>, if <math>v\neq w</math> and <math>(v,w)\notin A</math>.

==Induction step==
'''Abstract view:''' For all <math>v,w \in V</math>, we set <math>M^{i+1} (v,w) := \min \{ M^i (v,w) + L(u,w) \mid u \in V \}</math>.

(Note that <math>M^i (v,w) + L(u,w) = M^{i+1} (v,w)</math> is one of the arguments over which the minimum is taken, so the right-hand side is identical to <math>\min \{ M^i (v,w), \min \{ M^i (v,u)+ L(u,w) \mid u \in V \} \}</math>.)

'''Implementation:''' Obvious.

'''Correctness:''' Follows from the explanations of [[Paths#Powers of distance matrices|powers of the distance matrix]] and from the fact that a shortest path cannot have more than <math>|V|-1</math> arcs.

==Complexity==
'''Statement:''' The asymptotic complexity is <math>\Theta (n^4)</math> in the best and worst case.

'''Proof:''' The main loop terminates after <math>n-1</math> iterations. In each iteration of this loop, we update all <math>n^2</math> matrix entries, and computing one update value requires <math>\Theta (n)</math> steps.

Dijkstra

2014-10-21T17:48:46Z

Bencina: Tippfehler korrigiert

[[Category:Graph Algorithms]]
[[Category:All Pairs Shortest Paths]]
<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">Dijkstra</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/dijkstra-2310 Openlearnware]</div>
</div>

'''Dijstra's algorithm''' is a graph algortihm solving the single-source shortest-paths problem.

== Requirements ==

* directed Graph <math>G=(V,E)</math>
* weight function <math>w\colon E\to\mathbb R</math>
* <math>\forall(u,v)\in E\colon w(u,v)\geq 0</math>
* source <math>s\in V</math>
* Datastruct <math>S</math>
* Datastruct <math>Q</math>

== General information ==

'''Algorithmic problem:''' [[Single source shortest paths]]

'''Prerequisities:''' For all <math>\alpha \in A</math>, it is <math>l(a) \geq 0</math>.

'''Type of algortihm:''' loop

'''Auxiliary data:'''
# A temporary '''distance value''' <math>\delta(v) \in \R</math> for each node <math>v \in V</math>. At termination, it is <math>\delta(v) = \Delta(v)</math> for all <math>v \in V</math> where <math>\Delta(v)</math> is the shortest <math>(s,v)</math>-path.
# A [[bounded priority queue]] <math>Q</math> of size <math>|V|-1</math>, which contains nodes from <math>V</math> and takes their <math>\delta</math>-values as keys. The node with minimal key is returned.

== Abstract view ==

'''Invariant:''' After <math>i \geq 0</math> iterations:
# <math>Q</math> contains all nodes of <math>V</math> except <math>s</math> and <math>i</math> further nodes.
# For the nodes <math>v \in V</math> not in <math>Q</math>, it is <math>\delta(v) = \Delta(v)</math>.
# For the nodes <math>v \in V</math> in <math>Q</math>, <math>\delta(v)</math> is the length of a shortest <math>(s,v)</math>-path that solely contains nodes not in <math>Q</math> (except for <math>v</math> itself, of course). As usual, this means <math>\delta(v) = +\infty</math> if there is no such path.

In particular, it is <math>\delta(v) \geq \Delta(v)</math> for each node <math>v \in V</math>.

'''Variant:''' <math>i</math> increases by <math>1</math>.

'''Break condition:'''
* <math>Q = \empty</math>, which means that all nodes are reachable from <math>s</math> and have been processed;
* otherwise, if <math>\delta(v) = +\infty</math> for the next node <math>v</math> of <math>Q</math>, which means that <math>\delta(v) = + \infty</math> for '''every''' node in <math>Q</math> and hence none of the nodes in <math>Q</math> is reachable from <math>s</math>.

== Induction basis ==
=== Abstract view: ===
# All nodes of <math>V</math> except <math>s</math> have to be members of <math>Q</math>.
# Root <math>s</math> must have correct distance <math>\Delta(s) = 0</math>.
# The other nodes must meet Invariant #3.

=== Implementation: ===
# <math>\delta(s) := 0</math>;
# For all <math>a = (s,v) \in A</math>, set <math>\delta(v) := l(a)</math>.
# For all <math>v \in V\setminus\{s\}</math> with <math>(s,v) \notin A</math> set <math>\delta(v) := +\infty</math>.
# Insert all nodes in <math>V\setminus\{s\}</math> into <math>Q</math>.

=== Proof: ===
Obvious.

== Induction step ==

=== Abstract view: ===
One node is extracted from <math>Q</math>, and the distance values of the endnodes of its outgoing arcs are updated to meet Invariant #3.

=== Implementation: ===
# Extract the next node <math>v</math> from <math>Q</math>.
# For each outgoing arc <math>a = (v,w) \in A</math> such that <math>w \in Q</math>, set <math>\delta(w) := min\{\delta(w), \delta(v) + l(a)\}</math>.

=== Correctness: ===
The first invariant is trivially maintained. So we will focus on the second and third invariants.<br>
Consider the moment immediately before the <math>i</math>-iteration. The core of the proof is to show that <math>\delta(v) = \Delta(v)</math> hold at that moment (and hence forever). For a contradiction, suppose there is an <math>(s,v)</math>-path <math>p</math> whose length is strictly less than <math>\delta(v)</math>. The third invariant implies that <math>p</math> has nodes in <math>Q</math> beside <math>v</math>. Let <math>u</math> denote the first such node on <math>p</math>. Then none of the nodes on the subpath of <math>p</math> from <math>s</math> to <math>u</math> belonged to <math>Q</math> at that moment (except for <math>u</math> itself, of course). Due to the [[Paths|prefix property]], this subpath is a shortest <math>(s,u)</math>-path, so Invariant #3 implies <math>\delta(u) = \Delta(u)</math>. On the other hand, the specific choice of <math>v</math> implies <math>\delta(u) \geq \delta(v)</math>. In summary, the subpath of <math>p</math> from <math>s</math> to <math>w</math> is not shorter than <math>\delta(v)</math>. To obtain <math>l(p) < \delta(v)</math>, the subpath of <math>p</math> from <math>u</math> to <math>v</math> must have negative total length, which contradicts the prerequisite <math>l \geq 0</math>.<br>
Now we know <math>\delta(v) = \Delta(v)</math>. Therefore, <math>v</math> fulfills the statement of the second invariant after the <math>i</math>-th iteration. Of course, the second invariant is not violated by any other node either, and is thus maintained.<br>
For a node <math>w \in V</math> let <math>P_i (w)</math> denote the set of all <math>(s,w)</math>-paths such that no node (except for <math>w</math> itself) is in <math>Q</math> immediately after the <math>i</math>-th iteration. In particular, the statement of the third invariant means that <math>\delta(w)</math> is the length of a shortest path in <math>P_i (w)</math>. The induction hypothesis says that <math>\delta(w)</math> is the minimum length of all <math>(s,w)</math>-paths in <math>P_{i-1} (w)</math>. The difference <math>P_i (w) \setminus P_{i-1} (w)</math> consists of all <math>(s,w)</math>-paths such that <math>(v,w)</math> is the last arc and all nodes except for <math>v</math> and <math>w</math> belong to <math>V_{i-1}</math>. Therefore, the second step of the iteration incorporates <math>P_i (w) \setminus P_{i-1} (w)</math> in the computation of <math>\delta(w)</math> appropriately to maintain Invaraint #3.

== Complexity ==

'''Statement:''' The worst-case complexity is in <math>O(m+T(n)\cdot n)</math>, where <math>n = |V|</math> and <math>m = |A|</math>, and <math>T(n)</math> is the worst-case complexity for extraction/inserting nodes in <math>Q</math>.

'''Proof:''' Each node is inserted in and extracted from <math>Q</math> at most once, respectively, which gives <math>O(T(n) \cdot n)</math> in total. Also, each arc <math>(v,w) \in A</math> is touched at most once, namely
* in the initialization if <math>v = s</math>,
* when <math>v</math> is extracted from <math>Q</math> otherwise.

== Pseudocode ==

====DIJKSTRA(''G,w,s'')====

<code>
DIJKSTRA(''G,w,s'')
1 INITIALIZE-SINGLE-SOURCE(''G,s'')
2 ''S'' = ∅
3 ''Q'' = ''G.V''
4 '''while''' ''Q'' ≠ ∅
5 ''u'' = EXTRACT-MIN(''Q'')
6 ''S'' = ''S'' ∪ {''u''}
7 '''for''' each vertex ''v'' ∈ G.''Adj''[''u'']
8 RELAX(''u,v,w'')
</code>

====RELAX(''u,v,w'')====
<code>
RELAX(''u,v,w'')
1 '''if''' ''v.d'' > ''u.d'' + ''w''(''u,v'')
2 ''v.d'' = ''u.d'' + ''w''(''u,v'')
3 ''v.π'' = ''u''
</code>

<code>
====INITIALIZE-SINGLE-SOURCE(''G,s'')====
INITIALIZE-SINGLE-SOURCE(''G,s'')
1 '''for''' each vertex ''v'' ∈ ''G.V''
2 ''v.d'' = ∞
3 ''v.π'' = NIL
4 ''s.d'' = 0
</code>

== Further information ==
# We do not need to insert all nodes except for <math>s</math> in <math>Q</math>. In fact, it suffices to initially insert the endnodes of the outgoing arcs of <math>s</math> and, during an iteration, to insert the nodes of the outgoing arcs of the node that is being extracted from <math>Q</math>. In a sense, the nodes of <math>Q</math> then constitute the "frontierline" of the algorithm. We choose another variant on Dijkstra's algorithm mainly for simplicity of presentation.
# Clearly, Dijkstra's algorithm also solves the single-source single-target case. In this case, Dijkstra may safely terminate once has been extracted from <math>Q</math>. In fact, the loop invariant implies <math>\delta(t) = \Delta(t)</math> from then on. This variant on Dijkstra's algorithm is sometimes called the '''early termination variant'''.
# In the single-source single-target case, two searches may be applied simultaneously: one from <math>s</math> on <math>G</math>, the other one from <math>t</math> on the [[Basic graph definitions#Transpose of a graph|transpose]] of <math>G</math>. This variant is called '''bidirectional search'''. It terminates once one node has been seen by both searches. Then either the concatenation of the paths to this node from both searches is a shortest <math>(s,t)</math>-path, or such a path may be found among the paths of the following kind: There is an arc <math>(v,w)\in A</math> such that <math>v</math> has been seen in the forward search from the source and <math>w</math> has been seen in the backward search from <math>t</math>.
# In a scenario where we perform a large number of searches on the same graph and arc lengths, we do not need to touch the whole graph in each search:
## We change the algorithm as suggested by the first point: only keep the "frontierline" in <math>Q</math>.
## We also change the algorithm as suggested by the second point: terminate once <math>t</math> is processed.
## To avoid touching all nodes for initializing the <math>\delta</math>-values, we maintain sort of a '''version counter''', or '''time stamp''', for each node, which holds the ID of the last search that met this node. Whenever a node is met in a search and the nodes version counter does not equal the ID of the current search, the distance value of this node is regarded as <math>+ \infty</math> (no matter what its current value is).
# The early termination variant may be modified as follows: for and [[Paths|admissible distance function]] <math>h:V \to \R</math>, replace length <math>l</math> by <math>l_h</math> where <math>l_h(a) := l(a) + h(w) - h(v)</math> for each <math>a = (v,w) \in A</math>. This variant is usually called '''goal-directed search'''. The heuristic idea is that we (hopefully) reach <math> t</math> earlier because the arcs that roughly point towards <math>t</math> are shortened, and the arcs the roughly point in a direction away from <math>t</math> are lengthened.

Bubblesort

2014-10-13T14:29:56Z

Bencina: /* Gerneral information */ Tippfehler korrigiert

Dijkstra

2014-10-13T12:09:09Z

Bencina: /* Requirements */ Matheumgebungen eingefügt

Directed graph

2014-10-13T12:02:42Z

Bencina: Seite erstellt

==Definition==
A directed graph is a graph where every edge has a direction.

Bipartite graph

2014-10-13T11:33:05Z

Bencina: /* Absence of odd cycles */ Kleine formale Korrektur am Beweis vorgenommen.

[[Category:Checkup]]
[[Category:Background]]
[[File:Bipartite-graph.png|200px|thumb|right|A simple bipartite graph]]
==Definition==

An undirected graph <math>G=(V,E)</math> is called '''bipartite''' if there is a partition of <math>V</math>, <math>V=V_{1} \dot\cup V_{2}</math>, such that for every edge <math>\{ v,w \} \in E</math> it is <math>v \in V_{1} \Leftrightarrow w \in V_{2}</math>.

==Absence of odd cycles==
'''Theorem:''' An undirected graph <math>G=(V,E)</math> is bipartite if, and only if, <math>G</math> has no cycle of odd length.

'''Proof:'''
* First suppose <math>G</math> contains at least one cycle <math>v_{1} - v_{2} - ... - v_{k} - v_{1}</math> of odd length <math>k \in \N</math>. Without loss of generality, we assume <math>v_{1} \in V_{1}</math>. Then it is <math>v_{i} \in V_{1}</math> for all odd <math>i</math> and <math>v_{i} \in V_{2}</math> for all even <math>i</math>. The edge <math>\{ v,w \}</math> contradicts bipartiteness.
* Now suppose that <math>G</math> contains no cycle of odd length. We will prove bipartiteness constructively. Without loss of generality, we may assume that <math>G</math> is connected (otherwise, each connected component may be considered separately). We choose an node <math>v\in V</math>, which will be fix, and start with an arbitrary node <math>u \in V</math> and label each node "<math>x</math>" if its distance (smallest number of edges) from <math>v</math> is even, and "<math>y</math>" otherwise. Suppose for a contradiction that there is an edge <math>\{ v,w \}</math> such that both endnotes have the same label. Then the shortest paths from <math>u</math> to <math>v</math> and <math>w</math> plus this edge from an odd cycle (which is not simple but can be easily reduced to a simple cycle, which is odd again).

Bipartite graph

2014-10-13T11:26:59Z

Bencina: Tippfehler beseitigt

[[Category:Checkup]]
[[Category:Background]]
[[File:Bipartite-graph.png|200px|thumb|right|A simple bipartite graph]]
==Definition==

An undirected graph <math>G=(V,E)</math> is called '''bipartite''' if there is a partition of <math>V</math>, <math>V=V_{1} \dot\cup V_{2}</math>, such that for every edge <math>\{ v,w \} \in E</math> it is <math>v \in V_{1} \Leftrightarrow w \in V_{2}</math>.

==Absence of odd cycles==
'''Theorem:''' An undirected graph <math>G=(V,E)</math> is bipartite if, and only if, <math>G</math> has no cycle of odd length.

'''Proof:'''
* First suppose <math>G</math> contains at least one cycle <math>v_{1} - v_{2} - ... - v_{k} - v_{1}</math> of odd length <math>k \in \N</math>. Without loss of generality, we assume <math>v_{1} \in V_{1}</math>. Then it is <math>v_{i} \in V_{1}</math> for all odd <math>i</math> and <math>v_{i} \in V_{2}</math> for all even <math>i</math>. The edge <math>\{ v,w \}</math> contradicts bipartiteness.
* Now suppose that <math>G</math> contains no cycle of odd length. We will prove bipartiteness constructively. Without loss of generality, we may assume that <math>G</math> is connected (otherwise, each connected component may be considered separately). We start with an arbitrary node <math>u \in V</math> and label each node "<math>x</math>" if its distance (smallest number of edges) from <math>v</math> is even, and "<math>y</math>", otherwise. Suppose for a contradiction that there is an edge <math>\{ v,w \}</math> such that both endnotes have the same label. Then the shortest paths from <math>u</math> to <math>v</math> and <math>w</math> plus this edge from an odd cycle (which is not simple but can be easily reduced to a simple cycle, which is odd again).

B-tree: minimum

2014-10-13T11:22:51Z

Bencina: Beschreibung hinzugefügt

== General Information ==

'''Algorithmic Problem:'''

'''Type of algorithm:''' loop

'''Auxiliary data:''' A pointer p of type "pointer to a B-tree node".

== Abstract View ==
'''Invariant:''' Before and after each iteration:
# '''''p''''' points to some node '''''N''''' of the B-tree.

'''Variant:''' '''''p''''' is redirected from the current node '''''N''''' to the first child of the current node.

'''Break condition:'''
# '''''p''''' points to a leaf of the B-tree.

==Description of the algorithm==
To get the minimum of a B-Tree, you have to go to the leftest child while it exists.

== Pseudocode ==
<code>
Minimum(''x'')
1 '''while''' leaf(''x'') = false
2 ''x'' = c_0(''x'')
3 '''return''' key_0(''x'')
</code>

B-tree: minimum

2014-10-13T11:21:51Z

Bencina: /* Pseudocode */ Notation angepasst

== General Information ==

'''Algorithmic Problem:'''

'''Type of algorithm:''' loop

'''Auxiliary data:''' A pointer p of type "pointer to a B-tree node".

== Abstract View ==
'''Invariant:''' Before and after each iteration:
# '''''p''''' points to some node '''''N''''' of the B-tree.

'''Variant:''' '''''p''''' is redirected from the current node '''''N''''' to the first child of the current node.

'''Break condition:'''
# '''''p''''' points to a leaf of the B-tree.

== Pseudocode ==
<code>
Minimum(''x'')
1 '''while''' leaf(''x'') = false
2 ''x'' = c_0(''x'')
3 '''return''' key_0(''x'')
</code>

B-tree: maximum

2014-10-13T11:21:15Z

Bencina: Seite erstellt

== General Information ==

'''Algorithmic Problem:'''

'''Type of algorithm:''' loop

'''Auxiliary data:''' A pointer <math>p</math> of type "pointer to a B-tree node".

== Abstract View ==
'''Invariant:''' Before and after each iteration:
# <math>p</math> points to some node <math>N</math> of the B-tree.

'''Variant:''' <math>p</math> is redirected from the current node <math>p</math> to the first child of the current node.

'''Break condition:'''
# <math>p</math> points to a leaf of the B-tree.

== Description of the algorithm ==
To get the maximum of a B-Tree, you have to go to the rightest child while it exists.

== Pseudocode ==
<math>c_n(x)</math> is the rightest child of a node <math>x</math>.

<code>
Minimum(''x'')
1 '''while''' leaf(''x'') = false
2 ''x'' = c_n(''x'')
3 '''return''' key_n(''x'')
</code>

Bucketsort

2014-10-11T19:05:20Z

Bencina: Tippfehler beseitigt

[[Category:Sorting Algorithms]]
<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">Bucket 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/bucket-sort-1941 Openlearnware]</div>
</div>

== General information ==

'''Algorithmic problem:''' [[Sorting sequences of strings]]

'''Type of algorithm:''' loop

'''Axiliary data:'''
# An ordered sequence <math>S'</math> of strings, which will eventually hold the overall result of the algorithm.
# The '''buckets''', that is, an array <math>B</math> whose index range contains the ID range of <math>\Sigma</math> (e.g. 26 for the alphabet) and whose components are [[Sets and sequences|ordered sequences]] of strings.
# Let <math>N</math> denote the maximum length of an input string.
# An array <math>A</math> with index range <math>[1,\dots,N]</math> and [[Sets and sequences|multisets]] of strings as components.

== Abstract view ==

'''Invariant:''' After <math>i \geq 0</math> iterations:
# For <math>j \in \{1,\dots,N-i\}</math>, <math>A[j]</math> contains all input strings of length <math>j</math>.
# <math>S'</math> contains all other input strings, that is, the ones with length at least <math>N - i + 1</math>. The sequence <math>S'</math> is sorted according to the following definition of comparison: <math>str1 < str2</math> (resp. <math>str1 \leq str2</math>) means that the substring of <math>str1</math> starting at position <math>N - i + 1</math> is lexicographically smaller (resp., smaller or equal) than the substring of <math>str2</math> starting at position <math>N - i + 1</math>.
# All buckets are empty.

'''Variant:''' <math>i</math> increases by <math>1</math>.

'''Break condition: <math>i = N</math>.

== Induction basis ==

'''Abstract view:''' The auxiliary data must be initialized.

'''Implementation:'''
# <math>S' := \emptyset</math>
# For each <math>c \in \Sigma</math>, set <math>B[c] := \emptyset</math>
# For each <math>i \in \{1,\dots,N\}</math>, set <math>A[i] := \emptyset</math>
# Move each string <math>str</math> in <math>S</math> to <math>A[l(str)]</math> where <math>l(str)</math> denotes the length of <math>str</math>.

'''Proof:''' Obvious.

== Induction step ==
'''Abstract view:'''
# Move each string <math>str</math> in <math>A[N-i+1]</math> to <math>B[str[N-i+1]]</math>
# Afterwards: Append each string <math>str</math> in <math>S'</math> at the tail of <math>B[str[N - i + 1]]</math>. It is essential that the strings are considered in the order in which they are stored in <math>S'</math>. (Now <math>S'</math> is empty.)
# For each <math>c \in \Sigma</math> in ascending order: append <math>B[c]</math> at the tail of <math>S'</math> and make <math>B[c]</math> empty.

'''Implementation:''' Obvious

'''Correctness:''' We have to show that the relative order of each pair of strings, <math>str1</math> and <math>str2</math>, in the new sequence <math>S'</math> are correct. For that, we distinguish between four cases:
# If <math>str1[N-i+1] \neq str2[N-i+1]</math>, <math>str1</math> and <math>str2</math> are placed in different buckets in Step 3 of the <math>i</math>-th iteration, so they are correctly ordered according to the character at position <math>N - i + 1</math>.
# If <math>str1[N-i+1] = str2[N-i+1]</math> and both strings have length <math>N - i + 1</math>, their relative order is irrelevant, so nothing is to show.
# Next, consider the case that <math>str1[N-i+1] = str2[N-i+1]</math>, one string (say, <math>str1</math>) has length <math>N - i + 1</math> and the other one (<math>str2</math>) has a length strictly greater than <math>N - i + 1</math>. Since the strings of length <math>N - i + 1</math> are placed in their buckets prior to the longer strings (cf. Steps 1 and 2), <math>str2</math> appears after <math>str1</math>, which is correct.
# Finally, consider the case that <math>str1[N-i+1] = str2[N-i+1]</math>, and the lengths of both strings are larger than <math>N - i + 1</math>. Then the induction hypothesis guarantees the correct relative order due to the specific order in which the strings are considered in Step 2.

== Complexity ==
'''Statement:''' Let <math>M</math> denote the total sum of all input string lengths. Then the asymptotic complexity is in <math>\Theta(M)</math> in the best and the worst case.

'''Proof:''' Obviously, the preprocessing takes <math>O(M)</math> time.
In the main loop, each character of each string is read exactly once. Obviously, no operation is applied more often than the reading of single characters.

Selection sort

2014-10-11T18:55:08Z

Bencina: Tippfehler beseitigt

Mergesort

2014-10-11T18:51:49Z

Bencina: /* General Information */ Tippfehler beseitigt

Bubblesort

2014-10-11T18:49:05Z

Bencina: /* Complexity */ Tippfehler korrigiert

Quicksort

2014-10-11T16:01:24Z

Bencina: /* Proof: */ Weitere Tippfehler beseitigt

[[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.

Mergesort

2014-10-11T15:50:01Z

Bencina: /* Complexity */ Tippfehler beseitigt

Mergesort

2014-10-11T15:48:21Z

Bencina: /* Induction Step */ Tippfehler beseitigt

Quicksort

2014-10-11T15:47:02Z

Bencina: /* Proof: */ Tippfehler beseitigt

[[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 and 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.

Quicksort

2014-10-11T15:10:53Z

Bencina: /* Induction step */ Tippfehler korrigiert

[[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>) is in <mathO(|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 througout 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 and 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 throughtout 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.

Bubble

2014-10-11T15:01:48Z

Bencina: /* Complexity */ Schönheitskorrekturen (keine inhaltliche Änderung)

[[Category:Algorithm]]
[[Category:Auxiliary Algorithm]]

== General Information ==

'''Algorithmic problem:''' Moving the maximum element

'''Type of algorithm:''' loop

== Abstract View ==

'''Invariant:''' After <math>i \geq 0</math> iterations, the element at position <math>l + i</math> is the maximum of the elements at the position <math>l,\dots,l+i</math>.

'''Variant:''' <math>i</math> increases by <math>1</math>

'''Break condition:''' <math>i = r - l</math>

== Induction Basis ==

'''Abstract view:''' Nothing to do.

'''Implementation:''' Nothing to do.

'''Proof:''' Nothing to show.

== Induction Step ==

'''Abstract view:''' Exchange the elements at positions <math>l + i -1</math> and <math>l + i</math> if necessary.

'''Implementation:''' If <math>S[l+i-1] > S[l+i]</math>, swap <math>S[l+i-1]</math> and <math>S[l+i]</math>.

'''Correctness:''' The induction hypothesis implies that, immediately before the <math>i</math>-th iteration, <math>S[l+i-1]</math> is the maximum of the elements at the positions <math>l,\dots,l+i-1</math>. If <math>S[l+i-1] > S[l+i]</math>, <math>S[l+i-1]</math> is also the maximum out of <math>1,\dots,l+i</math> and should thus be moved to the position <math>l+i</math>. Otherwise <math>S[l+i]</math> is at least as large as all elements at positions <math>l+1,\dots,l+i-1</math> and should thus stay at position <math>l+i</math>.

== Complexity ==
'''Statement:''' The asymptotic complexity is <math>\Theta(r-l)</math> in the best and worst case.

'''Proof:''' Obvious.

Bubble

2014-10-11T14:57:43Z

Bencina: /* Induction Step */ Tippfehler beseitigt

[[Category:Algorithm]]
[[Category:Auxiliary Algorithm]]

== General Information ==

'''Algorithmic problem:''' Moving the maximum element

'''Type of algorithm:''' loop

== Abstract View ==

'''Invariant:''' After <math>i \geq 0</math> iterations, the element at position <math>l + i</math> is the maximum of the elements at the position <math>l,\dots,l+i</math>.

'''Variant:''' <math>i</math> increases by <math>1</math>

'''Break condition:''' <math>i = r - l</math>

== Induction Basis ==

'''Abstract view:''' Nothing to do.

'''Implementation:''' Nothing to do.

'''Proof:''' Nothing to show.

== Induction Step ==

'''Abstract view:''' Exchange the elements at positions <math>l + i -1</math> and <math>l + i</math> if necessary.

'''Implementation:''' If <math>S[l+i-1] > S[l+i]</math>, swap <math>S[l+i-1]</math> and <math>S[l+i]</math>.

'''Correctness:''' The induction hypothesis implies that, immediately before the <math>i</math>-th iteration, <math>S[l+i-1]</math> is the maximum of the elements at the positions <math>l,\dots,l+i-1</math>. If <math>S[l+i-1] > S[l+i]</math>, <math>S[l+i-1]</math> is also the maximum out of <math>1,\dots,l+i</math> and should thus be moved to the position <math>l+i</math>. Otherwise <math>S[l+i]</math> is at least as large as all elements at positions <math>l+1,\dots,l+i-1</math> and should thus stay at position <math>l+i</math>.

== Complexity ==
'''
Statement:''' The asymptotic complexity is <math>\Theta(r-l)</math> in the best and worst case.
'''
Proof:''' Obvious.