How to find number of expected swaps in bubble sort in better than O(n^2) time

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.

Solution

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.

Comments

[kilotaras]

I downvoted because its a question from a currently running contest.

[kilotaras]

Also it can be done in O(n logn)

[Richard Ye]

^ How? Care to give us a hint? I'm genuinely curious, and don't care about the contest :D

[kilotaras]

RMQ. If you want a full answer give me a ping after contest end.

[Jonathan Komar]

@kilotaras Where is the rule against "currently running contest"s on StackExchange?