Here is Bubble Sort with some code added:
# A is a list of length n.
counter = 0
for i=0 to n-2 inclusive
for j=0 to n-i-2 inclusive
ifA [j]> A[j+1]
swap A [j] and A[j+1]
counter = counter +1
end
end
end
For a list A of length n define:
C(A) = {(x, y)|0≤x≤n-1 and 0≤y≤n-1 and xA[y]}
Assuming A contains n distinct elements, if Bubble Sort is called on
A, prove that when the code ends counter equals the number of elements in C(A).