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

if $A[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)|0xn-1$ and $0yn-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).$