# Bubble sort: how to calculate amount of comparisons and swaps

For a given sequence 1, N ,2 ,N −1 ,3, N −2, ... I want to calculate the number of comparisons and swaps for bubble sort. How can I accomplish that using $$\theta ()$$ notation? I would know how to do it for any sequence, but not for a given one.

## 1 Answer

Number of swaps: The number of swaps in Bubble sort is exactly the number of inverted pairs, i.e. the number of pairs $$(i,j):i < j\wedge s[i]>s[j]$$. This number of pairs should be $$(n/2-1)+(n/2-2) + ... + 1$$ which is of the order of $$n^2$$.

Number of comparisons: This is of the order of $$n$$ times the number of passes through the list, which is of the order of $$n$$, as the element N needs to get to the end.

Therefore you have $$\Theta(n^2)$$ comparisons and swaps.

• As a side comment, @Marcel B even if the number of inversions is $\Theta(n^2)$ them can be computed in $O(n \log n)$. – Marcelo Fornet Oct 15 '19 at 18:38