Bubble sort

Bubble sort

General Information

Algorithmic problem: Sorting based on pairwise comparison

Type of algorithm: loop

Abstract View

Invariant: After $i\ge 0$ iterations, the elements of $S$ at the positions $|S|-i+1,\dots ,|S|$ are placed at their ocrrect positions in sorting order.

Variant: $i$ increases by $1$.

Break condition: $i=|S|-1$

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

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

Correctness: The loop invariant of the inner loop is this: after $m$ iterations of the inner loop, $S[m+1]$ is the maximum out of $S[1],\dots ,S[m+1]$. To see that invariant, note that the induction hypothesis implies for an iteration on index $j$ that $S[j-1]$ is the maxiumum out of $S[1],\dots ,S[j-1]$. So if $S[j-1]>S[j]$. $S[j-1]$ is also the maximum out of $S[1],\dots ,S[j]$. Therefore, swapping $S[j-1]$ and $S[j]$ maintains the invariant. On the other hand, if $S[j-1]\le S[j]$. $S[j]$ is already the maximum, so doing nothing maintains the invariant in this case.

Pseudocode

BUBBLESORT(A)
1 for i = 1 to "A.length" - 1 
2      for j = A.length downto i + 1
3            if A[j] < A[j - 1]
4                  exchange A[j] with A[j - 1]

Complexity

Statemen: The asymptotic complexity is in $\mathrm{\Theta }(T\cdot n^2)$ in the best and worst case, where $T$ is the complexity of the comparison.

Proof: The asymptotic complexity of the inner loop in the $i$-th iteration of the outer loop is in $\mathrm{\Theta }(T\cdot (n-i))$. Therefore, the total complexity is in $\mathrm{\Theta }(T\cdot \sum _{i=1}^{n-1}(n-i))=\mathrm{\Theta }(T\cdot \sum _{i=1}^{n-1}i)=\mathrm{\Theta }(T\cdot \frac{n(n-1)}{2})=\mathrm{\Theta }(T\cdot n^2)$