Bubble

From Algowiki
Jump to: navigation, search


General Information

Algorithmic problem: Moving the maximum element

Type of algorithm: loop

Abstract View

Invariant: After [math]i \geq 0[/math] iterations, the element at position [math]l + i[/math] is the maximum of the elements at the position [math]l,\dots,l+i[/math].

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

Break condition: [math]i = r - l[/math]

Induction Basis

Abstract view: Nothing to do.

Implementation: Nothing to do.

Proof: Nothing to show.

Induction Step

Abstract view: Exchange the elements at positions [math]l + i -1[/math] and [math]l + i[/math] if necessary.

Implementation: If [math]S[l+i-1] \gt S[l+i][/math], swap [math]S[l+i-1][/math] and [math]S[l+i][/math].

Correctness: The induction hypothesis implies that, immediately before the [math]i[/math]-th iteration, [math]S[l+i-1][/math] is the maximum of the elements at the positions [math]l,\dots,l+i-1[/math]. If [math]S[l+i-1] \gt S[l+i][/math], [math]S[l+i-1][/math] is also the maximum out of [math]1,\dots,l+i[/math] and should thus be moved to the position [math]l+i[/math]. Otherwise [math]S[l+i][/math] is at least as large as all elements at positions [math]l+1,\dots,l+i-1[/math] and should thus stay at position [math]l+i[/math].

Complexity

Statement: The asymptotic complexity is [math]\Theta(r-l)[/math] in the best and worst case.

Proof: Obvious.