6
$\begingroup$

The well-known Bubblesort algorithm sorts a list $a_1, a_2, . . . , a_n$ of numbers by repeatedly swapping adjacent numbers that are inverted (i.e., in the wrong relative order) until there are no remaining inversions. (Note that the number of swaps required does not depend on the order in which the swaps are made.) Suppose that the input to Bubblesort is a random permutation of the numbers $a_1, a_2, . . . , a_n$ , so that all $n!$ orderings are equally likely, and that all the numbers are distinct. What is the expected number of swaps performed by Bubblesort?

$\endgroup$
  • $\begingroup$ similarly, the variance? i feel like using a similar uniform distribution method $\endgroup$ – Charlie Tian Feb 23 '18 at 8:58
7
$\begingroup$

It should be equal to the expected number of inversions in a random permutation. Recall that an inversion is a pair $(i,j)$ with $\pi(i)>\pi(j)$. It's not hard to show that if a permutation has $N$ inversions in it, then that's the length of Bubble-sorting it as well. To see this, show that the identity permutation is the only permutation with 0 inversions and that performing one step of bubble-sort lowers the inversion number by exactly 1.

Calculating the expected number of inversions: For a permutation of length $n$, let $I_{ij}=1$ if $(i,j)$ is an inversion. Then $\mathbb{E}[I_{i,j}]=P((i,j)\mbox{ is an inversion})=1/2$. This is easy to see by symmetry: for any pair $(i,j)$ that's an inversion, $(j,i)$ is not an inversion.

Then the expected number of inversions is:

$$\mathbb{E}[\sum_{i=1}^n\sum_{j>i}^n I_{ij}]=\sum_{i=1}^n\sum_{j>i}^n \frac{1}{2}=\binom{n}{2}\frac{1}{2}=\frac{n(n-1)}{4}$$.

You can also calculate this another way. Every permutation $\pi$ with $N$ inversions can be read backwards to give a permutation with $\binom{n}{2}-N$ inversions. This gives a 1-1 map between permutations with $N$ inversions and $\binom{n}{2}-N$ inversions. Then by symmetry it's clear that the expected value is $\frac{1}{2}\binom{n}{2}$.

$\endgroup$
  • 3
    $\begingroup$ +1 For the last paragraph. The same argument goes thru with all finite groups generated by reflections. $\endgroup$ – Jyrki Lahtonen Jul 27 '13 at 21:15
  • $\begingroup$ This question shows up every once in a while. Here is some more material on this subject. $\endgroup$ – Marko Riedel Jul 28 '13 at 19:12

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.