Danzev's blog

Just a simple bubble sort question
By Danzev, history, 5 years ago, In English

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)$$$?

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Count the inversions

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply