How to find number of expected swaps in bubble sor

Question

I am stuck on problem http://www.codechef.com/JULY12/problems/LEBOBBLE Here it is required to find number of expected swaps.

I tried an O(n^2) solution but it is timing out.

The code is like:

swaps = 0
for(i = 0;i < n-1;i++)
    for(j = i+1;j<n;j++)
    {
        swaps += expected swap of A[i] and A[j]
    }

Since probabilities of elements are varying, so every pair is needed to be compared. So according to me the above code snippet must be most efficient but it is timing out.

Can it be done in O(nlogn) or it any complexity better than O(n^2). Give me any hint if possible.

Answer 1

Use divide and conquer

divide: size of sequence n to two lists of size n/2 conquer: count recursively two lists combine: this is a trick part (to do it in linear time)

combine use merge-and-count. Suppose the two lists are A, B. They are already sorted. Produce an output list L from A, B while also counting the number of inversions, (a,b) where a is-in A, b is-in B and a > b.

The idea is similar to "merge" in merge-sort. Merge two sorted lists into one output list, but we also count the inversion.

Everytime a_i is appended to the output, no new inversions are encountered, since a_i is smaller than everything left in list B. If b_j is appended to the output, then it is smaller than all the remaining items in A, we increase the number of count of inversions by the number of elements remaining in A.

merge-and-count(A,B) ; A,B two input lists (sorted) ; C output list ; i,j current pointers to each list, start at beginning ; a_i, b_j elements pointed by i, j ; count number of inversion, initially 0

while A,B != empty append min(a_i,b_j) to C if b_j < a_i count += number of element remaining in A j++ else i++ ; now one list is empty append the remainder of the list to C return count, C

With merge-and-count, we can design the count inversion algorithm as follows:

sort-and-count(L) if L has one element return 0 else divide L into A, B (rA, A) = sort-and-count(A) (rB, B) = sort-and-count(B) (r, L) = merge-and-count(A,B) return r = rA+rB+r, L

T(n) = O(n lg n)

Answer 2

Alright, let's think about this.

We realize that every number needs to be eventually swapped with every number after it that's less than it, sooner or later. Thus, the total number of swaps for a given number is the total number of numbers after it which are less than it. However, this is still O(n^2) time.

For every pass of the outer loop of bubble sort, one element gets put in the correct position. Without loss of generality, we'll say that for every pass, the largest element remaining gets sorted to the end of the list.

So, in the first pass of the outer loop, the largest number is put at the end. This takes q swaps, where q is the number of positions the number started away from the final position.

Thus, we can say that it will take q₁+q₂+ ... +q_n swaps to complete this bubble sort. However, keep in mind that with every swap, one number will be taken either one position closer or one position farther away from their final positions. In our specific case, if a number is in front of a larger number, and at or in front of its correct position, one more swap will be required. However, if a number is behind a larger number and behind it's correct position, one less swap will be required.

We can see that this is true with the following example:

   5 3 1 2 4
=> 3 5 1 2 4
=> 3 1 5 2 4
=> 3 1 2 5 4
=> 3 1 2 4 5
=> 1 3 2 4 5
=> 1 2 3 4 5 (6 swaps total)

"5" moves 4 spaces. "3" moves 1 space. "1" moves 2 spaces. "2" moves 2 spaces. "4" moves 1 space. Total: 10 spaces.

Note that 3 is behind 5 and in front of its correct position. Thus one more swap will be needed. 1 and 2 are behind 3 and 5 -- four less swaps will be needed. 4 is behind 5 and behind its correct position, thus one less swap will be needed. We can see now that the expected value of 6 matches the actual value.

We can compute Σq by sorting the list first, keeping the original positions of each of the elements in memory while doing the sort. This is possible in O(nlogn + n) time.

We can also see what numbers are behind what other numbers, but this is impossible to do in faster than O(n^2) time. However, we can get a faster solution.

Every swap effectively moves two numbers number needs to their correct positions, but some swaps actually do nothing, because one be eventually swapped with every number gets closerafter it that's less than it, and another gets farthersooner or later. The first swap in our previous exampleThus, between "3" and "5" is the only example of this in our example.

We have to calculate how many total number of said swaps that there are. This is left as an exercise to the reader, but here's one last hint: you only have to loop through the first half of the list. Though this for a given number is still, in the end O(n^2), we only have to do O(n^2) operations on the first half total number of the list, making numbers after it much faster overall.