# What is the expected number of swaps performed by Bubblesort?

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?

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

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.
$$\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}$.