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
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ 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)$. $\endgroup$ Commented Oct 15, 2019 at 18:38