Bubble Sort


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.

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[j],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: