Given an array $A$ of $N$ integers, each element in the array can be increased by a fixed number $b$ with some probability $p[i]$, $0 \leq i < n$. I have to find the expected number of swaps that will take place to sort the array using bubble sort.

I've tried the following:

  1. The probability for an element $A[i] > A[j]$ for $i < j$ can be calculated easily from the given probabilities.

  2. Using the above, I have calculated the expected number of swaps as:

    double ans = 0.0;
    for ( int i = 0; i < N-1; i++ ){
        for ( int j = i+1; j < N; j++ ) {
            ans += get_prob(A[i], A[j]); // Computes the probability of A[i]>A[j] for i < j.

Basically I came to this idea because the expected number of swaps can be calculated by the number of inversions of the array. So by making use of given probability I am calculating whether a number $A[i]$ will be swapped with a number $A[j]$.

Note that the initial array elements can be in any order, sorted or unsorted. Then each number can change with some probability. After this I have to calculate the expected number of swaps.

I have posted a similar question before but it did not had all the constraints.

I did not get any good hints on whether I am even on the right track or not, so I listed all the constraints here. Please give me some hints if I am thinking of the problem in an incorrect way.

  • 6
    $\begingroup$ Cute tpyo in the title, though. $\endgroup$
    – JeffE
    Jul 5, 2012 at 11:46
  • $\begingroup$ Don't you mean, give a sorted array of N integers, each element... Also the range of the numbers in the initial array and the differences between them, relative to b seem to be missing. $\endgroup$ Jul 5, 2012 at 18:17
  • $\begingroup$ Keep in mind that for this kind of analysis, you have to make very clear what particular "implementation" if the Bubblesort idea you consider. It would be best if you gave the algorithm in pseudo code. $\endgroup$
    – Raphael
    Jul 9, 2012 at 8:41
  • $\begingroup$ This problem is from an ongoing contest on codechef site codechef.com/JULY12/problems/LEBOBBLE I'll be happy to post my approach after the contest. $\endgroup$ Jul 9, 2012 at 20:35

1 Answer 1


Let $\sf{Bubble Sort}$ be defined as the following:

for (j = A.length; j > 1; j--)
    for (i = 0; i < j - 1; i++)
        if (A[i] > 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 < x_i$ for some $i < 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<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<j} I_{ij}] = \sum_j \sum_{i<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 < x_i$ and half of the time $x_i < x_j$ for $i \neq j$.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.