0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\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$ – Marcelo Fornet Oct 15 '19 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy