# Bubblesort

## General information

Algorithmic problem: Sorting based on pairwise comparison

Type of algorithm: loop

## Abstract view

Invariant: After $i \geq 0$ iterations, the elements of $S$ at the positions $|S| - i + 1,\dots,|S|$ are placed at their correct 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] \gt 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,\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 maximum out of $S,\dots,S[j-1]$. So, if $S[j-1] \gt S[j]$, $S[j-1]$ is also the maximum out of $S,\dots,S[j]$. Therefore, swapping $S[j-1]$ and $S[j]$ maintains the invariant. On the other hand, if $S[j-1] \leq S[j]$, $S[j]$ is larger than $S,\ldots,S[j-2]$ as well (due to the induction hypothesis), so doing nothing indeed maintains the invariant in this case.

## Complexity

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

Proof: The asymptotic complexity of the inner loop in the $i$-th iteration of the outer loop is in $\Theta(T\cdot(n-i))$. Therefore, the total complexity is in $\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)$.