Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

migrated from cstheory.stackexchange.com Jul 5 '12 at 15:26

This question came from our site for theoretical computer scientists and researchers in related fields.

6  
Cute tpyo in the title, though. –  JeffE Jul 5 '12 at 11:46
    
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. –  Danny Varod Jul 5 '12 at 18:17
    
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. –  Raphael Jul 9 '12 at 8:41
    
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. –  rizwanhudda Jul 9 '12 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}$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.