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 of [math]S[/math] at the positions [math]|S| - i + 1,\dots,|S|[/math] are placed at their correct positions 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: Step-by-step, move the maximum element seen so far to the position [math]|S| - i + 1[/math].

Implementation: For [math]j := 2,\dots,|S|-i+1[/math] (in this order): If [math]S[j-1] \gt S[j][/math], swap [math]S[j-1][/math] and [math]S[j][/math].

Correctness: The loop invariant of the inner loop is this: after [math]m[/math] iterations of the inner loop, [math]S[m+1][/math] is the maximum out of [math]S[1],\dots,S[m+1][/math] To see that invariant, note that the induction hypothesis implies for an iteration on index [math]j[/math] that [math]S[j-1][/math] is the maximum out of [math]S[1],\dots,S[j-1][/math]. So, if [math]S[j-1] \gt S[j][/math], [math]S[j-1][/math] is also the maximum out of [math]S[1],\dots,S[j][/math]. Therefore, swapping [math]S[j-1][/math] and [math]S[j][/math] maintains the invariant. On the other hand, if [math]S[j-1] \leq S[j][/math], [math]S[j][/math] is larger than [math]S[1],\ldots,S[j-2][/math] as well (due to the induction hypothesis), so doing nothing indeed maintains the invariant in this 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 a comparison.

Proof: The asymptotic complexity of the inner loop in the [math]i[/math]-th iteration of the outer loop is in [math]\Theta(T\cdot(n-i))[/math]. Therefore, the total complexity is in [math]\Theta\left(\sum_{i=1}^{n-1} T\cdot(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(T\cdot n^2)[/math].