### Danzev's blog

By Danzev, history, 6 weeks ago, ,

Given an array $a_1,a_2,\dots,a_n$, $a_i=i$ and a permutation of this array $p_1,p_2,\dots,p_n$. We sort this permutation to get initial array using bubble sort.

Question: how to calculate a number of swaps in $O(n)$ instead $O(n^2)$?

• +5

 » 6 weeks ago, # |   +13 Count the inversions
•  » » 6 weeks ago, # ^ |   0 Counting inversions would take O(nlogn).
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +5 Edit: my solution is wrong.
•  » » » » 6 weeks ago, # ^ |   0 Yeah, Thanks for explaining.
•  » » » » 6 weeks ago, # ^ |   +68 Could you please share code?
•  » » » » » 6 weeks ago, # ^ |   0 I realized I made a wrong observation. So my solution would not work. Sorry about that.
 » 6 weeks ago, # | ← Rev. 3 →   0 In case you still haven't gotten your answer, the following takes $O(n \log n)$: perhaps the easiest way is to use a segment tree. First, initialize cnt=0. Process the array in order from left to right. When we get to a new element with value x, do the operation update(x,1) (add 1 to location x in the tree). Then, query for the sum from one more than that element's value to the maximum value in the array, and add that to a running inversion count: cnt += query(x+1, N) (where N is the maximum possible value in the array). The answer is cnt after you've processed the entire array.