Selection sort: Difference between revisions

From Algowiki
Jump to navigation Jump to search
m (Luedecke moved page Selection Sort to Selection sort)
No edit summary
 
(11 intermediate revisions by 3 users not shown)
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 39: Line 39:
# Swap <math>S[m]</math> and <math>S[|S|-i+1]</math>.
# Swap <math>S[m]</math> and <math>S[|S|-i+1]</math>.


'''Correctness:''' Follows immediately from the invariant of the inner loop: <math>S[m]</math> is the maximum element out of <math>S[1],\dots,S[j]</math>.
'''Correctness:''' Obviously: <math>S[m]</math> is the maximum element out of <math>S[1],\dots,S[j]</math>.


== 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(T\cdot n^2)</math> in the best and worst case, where <math>T</math> is the complexity of the comparison.


'''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 <math>i</math>-th iteration is in <math>\Theta(T\cdot(n - i))</math>. Therefore, the total complexity is in <math>\Theta\left(T\cdot\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(T\cdot\sum_{i=1}^{n-1} i \right) = \Theta\left(T\cdot\frac{n(n-1)}{2} \right) = \Theta\left(T\cdot n^2\right)</math>.

Latest revision as of 11:05, 30 June 2015

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:

  1. Set [math]\displaystyle{ m := 1 }[/math]
  2. 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].
  3. Swap [math]\displaystyle{ S[m] }[/math] and [math]\displaystyle{ S[|S|-i+1] }[/math].

Correctness: Obviously: [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(T\cdot n^2) }[/math] in the best and worst case, where [math]\displaystyle{ T }[/math] is the complexity of the comparison.

Proof: The asymptotic complexity of the [math]\displaystyle{ i }[/math]-th iteration is in [math]\displaystyle{ \Theta(T\cdot(n - i)) }[/math]. Therefore, the total complexity is in [math]\displaystyle{ \Theta\left(T\cdot\sum_{i=1}^{n-1} (n-i) \right) = \Theta\left(T\cdot\sum_{i=1}^{n-1} i \right) = \Theta\left(T\cdot\frac{n(n-1)}{2} \right) = \Theta\left(T\cdot n^2\right) }[/math].