Expected number of swaps in bubble sort
Let $\sf{Bubble Sort}$ be defined as the following:

for (j = A.length; j &gt; 1; j--)
    for (i = 0; i &lt; j - 1; i++)
        if (A[i] &gt; A[i + 1])
            swap(i, i + 1, A)


Given some permutation $x_1, \cdots, x_n$, an inversion is said to have occurred if $x_j &lt; x_i$ for some $i &lt; j.$ We see that $\sf{Bubble Sort}$ performs an inversion check for each pair, and if so, performs a swap. Let $X$ be the number of swaps. It is not hard to see in the worst case there are $X = \binom{n}{2}$ possible swaps made. But we are interested in the expected case, which we can compute by defining $X$ in terms of inversions in $\sf{Bubble Sort}$.

Now let $X = \sum_j \sum_{i&lt;j} I_{ij}$ where $I_{ij}$ is the indicator variable that there exists an inversion for some pair $(i,j)$. The expectation is defined as $E[X] = E[\sum_j \sum_{i&lt;j} I_{ij}] = \sum_j \sum_{i&lt;j} E[I_{ij}]$. We now need to determine $P\{I_{ij}\}$.

When assuming any possible permutation as input, each with uniform probability, it can been shown that $P\{I_{ij}\} = \frac{1}{2}$. The reasoning behind this is that under any possible permutation, half of the time $x_j &lt; x_i$ and half of the time $x_i &lt; x_j$ for $i \neq j$.

Returning to our expectation calculation we see that $E[X] = \sum_j \sum_{i&lt;j}E[I_{ij}] = \sum_j \sum_{i&lt;j} \frac{1}{2} = \binom{n}{2} \cdot \frac{1}{2} = \frac{n(n-1)}{4}$