Number Of Inversion

Theory

What is Inversion??

한국어로는 역전이라고도 한다.
배열 $A=Array$ 에 대해 $i, j$ 는 $0 <= i,j<= length(A)$ 이다.

• 역전은 아래를 만족함.
  • $A[i] < A[j]$

다시말해, Number of Inversion 은 이 역전의 개수를 세는 문제이다.

How to count Number of Inversion?

필자는 Merge sort로 구현하는 아이디어를 떠올렸다. 정렬하는 과정에서 카운팅 하는 것이 쉽다는 힌트를 보고 왜 그런가 정말 오래 고민했다.

아무튼, Merge Sort를 할 때는 항상 아래의 과정을 따른다.

각 요소를 합치는 과정에서 가장 작은것부터 비교가 이루어지며, $Array2$에서 이를 활용해 만약 $Array1$의 다음으로 선택할 가장 작은 요소가, $Array2$의 그것보다 크다면, $Array1$의 남은 요소 수 만큼 역전 쌍이 상기게 된다.

여기까지 다다르고 나면, 머지소트로 어떻게 구현해야 하는지 감이 올 것이다.

Sample code

백준 1517 버블 소트번이 적절한 문제로 보여, 해당 문제의 solution중 일부를 담았다.

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int>v,tmp;
long long cnt;

void merge(int s, int e) {
    int mid = (s + e) / 2;
    int i = s, j = mid + 1, k = s;
    while (i <= mid && j <= e) {
        if (v[i] > v[j]) { // There is an Inversion! 
            cnt+=mid-i+1;
            tmp[k++] = v[j++];
        }
        else {
            tmp[k++] = v[i++];
        }
    }
    while (i <= mid)tmp[k++] = v[i++];
    while (j <= e)tmp[k++] = v[j++];
    for (int p = s; p <= e; p++)v[p] = tmp[p];
}

void partition(int s, int e) {  // s to e-1
    if (s >= e)return;
    int mid = (s + e) / 2;
    partition(s, mid);
    partition(mid + 1, e);
    merge(s, e);
}