# Bubble Sort

Algorithm.

```for i = n downto 2 do for j = 1 to i-1 do if A[j] > A[j+1] then A[j] <-> A[j+1]```

Analysis (comparisons). The conditional is executed every iteration of the inner loop. Therefore, the number of comparisons is dependent only on the size of the list $n$.

• $\underset{i=2}{\overset{n}{\Sigma }}\underset{j=1}{\overset{i-1}{\Sigma }}1$
• $=\frac{\left(n-1\right)n}{2}$

Analysis (exchanges). There is one central observation that makes counting exchanges incredibly straightforward. This is the bijection between transpositions and exchanges.

A transposition is a pair of elements that are out-of-place. The exchange operation occurs under a conditional that requires that $\left(A\left[j\right],A\left[j+1\right]\right)$ be a transposition. Therefore, every exchange has a corresponding transposition. Because bubble sort is a correct algorithm, every transposition must be resolved to achieve a sorted list. Therefore, every transposition has a corresponding exchange.

Since there is a bijection, to count exchanges, we can count transpositions instead:

• The best case occurs when the list is already sorted. No transpositions, no exchanges.
• The worst case is where the list is reversed. Every element is a transposed with respect to every other element. Since every pair of elements in our list is transposed, we count all possible pairs. This is $\left(\genfrac{}{}{0}{}{n}{2}\right)$.
• The average case occurs in a randomly distributed list. The probability that any pair of elements will be transposed is $\frac{1}{2}$. Since every transposed pair requires one exchange we get $\frac{1}{2}\left(\genfrac{}{}{0}{}{n}{2}\right)$.