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]
The conditional is executed every iteration of the inner loop. Therefore, the number of comparisons is dependent only on the size of the list .
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 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 .
- The average case occurs in a randomly distributed list. The probability that any pair of elements will be transposed is . Since every transposed pair requires one exchange we get .