Selection sort

From Algowiki
Jump to: navigation, search

General information

Algorithmic problem: Sorting based on pairwise comparison

Type of algorithm: loop

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.

Variant: [math]i[/math] increases by [math]1[/math].

Break condition: [math]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]S[1],\dots,S[|S|-i+1][/math] and then move it, by a swap, to position [math]|S|-i+1[/math].

Implementation:

  1. Set [math]m := 1[/math]
  2. For all [math]j=2,\dots,|S|-i+1[/math]: If [math]S[j] \gt S[m][/math] set [math]m := j[/math].
  3. Swap [math]S[m][/math] and [math]S[|S|-i+1][/math].

Correctness: Obviously: [math]S[m][/math] is the maximum element out of [math]S[1],\dots,S[j][/math].

Complexity

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