Bubblesort: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(5 intermediate revisions by 2 users not shown)
Line 8: Line 8:
</div>
</div>


== Gerneral information ==
== General information ==


'''Algorithmic problem:''' [[Sorting based on pairwise comparison]]
'''Algorithmic problem:''' [[Sorting based on pairwise comparison]]
Line 35: Line 35:
'''Implementation:''' For <math>j := 2,\dots,|S|-i+1</math> (in this order): If <math>S[j-1] > S[j]</math>, swap <math>S[j-1]</math> and <math>S[j]</math>.
'''Implementation:''' For <math>j := 2,\dots,|S|-i+1</math> (in this order): If <math>S[j-1] > 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] > 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 already the maximum, so doing nothing maintains the invariant in this case.
'''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] > 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.


== Complexity ==
== Complexity ==


'''Statement:''' The asymptotic complexity is in <math>\Theta(^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 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(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(n^2)</math>.
'''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>.

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

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

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

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 a comparison.

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(T\cdot(n-i)) }[/math]. Therefore, the total complexity is in [math]\displaystyle{ \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].