Geek asks and answers

The expected number of swaps in sorting bubbles

Possible duplicate:
Number of swaps in Bubble Sort

The problem is summarized below:
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 <= i <n. I have to find the expected number of swaps that will take place to sort the array using bubble sort .

I tried the following:

1) The probability for the element A [i]> A [j] for i <j is easily calculated from the given probabilities. 2) Using the above, I 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.

I basically came up with this idea because the expected number of swaps can be calculated from the number of inversions of the array. Therefore, using this probability, I calculate whether the number A [i] will be replaced by the number A [j].

I already posted a similar question , but it did not have all the restrictions.

I had no good hint as to whether I am really on the right track or not, so I have listed all the restrictions here. Please give me some suggestions if I misrepresent the problem.

+3
source share
1 answer

The expected number of swaps for a given element is simply the expected number of elements to the left of it that are larger than it.

, linearity.

, , a_3. , ,

E [# a_3] = E [a_0 > a_3] + E [a_1 > a3] + E [a_2 > a_3]

.

- , ( ).

+2

More articles:


All Articles