# 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{(n-1)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 $(A\left[j\right],A[j+1])$ 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{}{}{0ex}{}{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{}{}{0ex}{}{n}{2}\right)$.