Selection sort

Selection Sort

whatever

Openlearnware

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 |S|-i+1.

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: 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]