Блог пользователя Danzev

Just a simple bubble sort question
Автор Danzev, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Count the inversions

→ Ответить
»
4 года назад, # |
← 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.

→ Ответить