Selection sort: Difference between revisions
m (Luedecke moved page Selection Sort to Selection sort) |
m (Tippfehler beseitigt) |
||
| Line 16: | Line 16: | ||
== Abstract view == | == Abstract view == | ||
'''Invariant:''' After <math>i \geq 0</math>iterations: The elements at positions <math>|S|-i+1,\dots,|S|</math> are correctly placed in sorting order. | '''Invariant:''' After <math>i \geq 0</math> iterations: The elements at positions <math>|S|-i+1,\dots,|S|</math> are correctly placed in sorting order. | ||
'''Variant:''' <math>i</math> increases by <math>1</math> | '''Variant:''' <math>i</math> increases by <math>1</math>. | ||
'''Break condition:''' <math>i = |S| - 1</math>. | '''Break condition:''' <math>i = |S| - 1</math>. | ||
| Line 32: | Line 32: | ||
== Induction step == | == Induction step == | ||
'''Abstract view:''' Identify the maximum out of <math>S[1],\dots,S[|S|-i+1]</math> and then move it, by a swap, to position |S|-i+1. | '''Abstract view:''' Identify the maximum out of <math>S[1],\dots,S[|S|-i+1]</math> and then move it, by a swap, to position <math>|S|-i+1</math>. | ||
'''Implementation:''' | '''Implementation:''' | ||
| Line 43: | Line 43: | ||
== Complexity == | == Complexity == | ||
'''Statement: The asymptotic complexity is in <math>\Theta(n^2)</math> in the best and worst case. | '''Statement:''' The asymptotic complexity is in <math>\Theta(n^2)</math> in the best and worst case. | ||
'''Proof:''' The asymptotic complexity of the inner loop in the <math>i</math>-th iteration of the outer loop is in <math>\Theta(n - i)</math>. Therefore, the total complexity is in <math>\Theta\left(\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(\sum_{i=1}^{n-1} i \right) = \Theta\left(\frac{n(n-1)}{2} \right) = \Theta\left(n^2\right)</math> | '''Proof:''' The asymptotic complexity of the inner loop in the <math>i</math>-th iteration of the outer loop is in <math>\Theta(n - i)</math>. Therefore, the total complexity is in <math>\Theta\left(\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(\sum_{i=1}^{n-1} i \right) = \Theta\left(\frac{n(n-1)}{2} \right) = \Theta\left(n^2\right)</math>. | ||
Revision as of 18:55, 11 October 2014
General information
Algorithmic problem: Sorting based on pairwise comparison
Type of algorithm: loop
Abstract view
Invariant: After [math]\displaystyle{ i \geq 0 }[/math] iterations: The elements at positions [math]\displaystyle{ |S|-i+1,\dots,|S| }[/math] are correctly placed in sorting order.
Variant: [math]\displaystyle{ i }[/math] increases by [math]\displaystyle{ 1 }[/math].
Break condition: [math]\displaystyle{ i = |S| - 1 }[/math].
Induction Basis
Abstract view: Nothing to do.
Implementation: Nothing to do.
Proof: Nothing to show.
Induction step
Abstract view: Identify the maximum out of [math]\displaystyle{ S[1],\dots,S[|S|-i+1] }[/math] and then move it, by a swap, to position [math]\displaystyle{ |S|-i+1 }[/math].
Implementation:
- Set [math]\displaystyle{ m := 1 }[/math]
- For all [math]\displaystyle{ j=2,\dots,|S|-i+1 }[/math]: If [math]\displaystyle{ S[j] \gt S[m] }[/math] set [math]\displaystyle{ m := j }[/math].
- Swap [math]\displaystyle{ S[m] }[/math] and [math]\displaystyle{ S[|S|-i+1] }[/math].
Correctness: Follows immediately from the invariant of the inner loop: [math]\displaystyle{ S[m] }[/math] is the maximum element out of [math]\displaystyle{ S[1],\dots,S[j] }[/math].
Complexity
Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(n^2) }[/math] in the best and worst case.
Proof: The asymptotic complexity of the inner loop in the [math]\displaystyle{ i }[/math]-th iteration of the outer loop is in [math]\displaystyle{ \Theta(n - i) }[/math]. Therefore, the total complexity is in [math]\displaystyle{ \Theta\left(\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(\sum_{i=1}^{n-1} i \right) = \Theta\left(\frac{n(n-1)}{2} \right) = \Theta\left(n^2\right) }[/math].