[알고리즘] Inversion Count (Merge Sort)

배열에 [1,3,2,5,7,6] 라는 값이 들어있을 때 자신의 앞에 있는 수 중에 자신보다 크기가 큰 수의 갯수를 찾으려면 어떻게 해야할까? 즉, i < j && A[i] > A[j] 를 만족하는 갯수를 찾는것이다. 

1은 맨 앞에 있으므로 1보다 앞에 있는 수 중 자신보다 큰 수는 없다.
3은 두번째에 위치하지만 앞에 있는 수가 자신보다 작으므로 자신보다 큰 수는 없다.
2는 자신의 앞에 자신보다 큰 3이라는 숫자가 있다.

이런식으로 배열 원소의 각각의 위치에서 자신보다 "앞에 있는" 수 중에 자신보다 "큰" 수를 찾고 싶을때 쓰인다.

쉽게 떠올릴 수 있는 가장 일반적인 방법은 이중for문을 돌면서 각각의 원소마다 자신보다 큰 수의 갯수를 찾으면 될것이다. 그러나 이건 O(N^2)의 시간복잡도를 가지므로 효율적인 방법이라 볼 수 없다.

이 문제를 해결하기 위해 사용하는 방법이 inversion count이다. 새로운 알고리즘 이라기 보다는 O(NlogN)의 시간복잡도를 가지는 Merge Sort(병합정렬)을 응용하는 방법이라고 보면 된다.

---

위 사진은 Merge Sort의 과정을 그림으로 나타낸 것이다.

머지소트는 배열을 나누어 합치며 정렬을 수행 한다. 위 사진에서 맨 위를 1번째 단계라고 하면 4번째 단계까지 배열을 나누는 작업을 수행하고 5번째 단계부터 나뉘어진 배열을 합치며 정렬하는 작업을 수행한다.

inversion count계산을 이해하기 위해선 먼저 배열들이 어떻게 병합되는지를 이해해야 한다.
두 개로 나누어진 서브배열을 A,B라고 하면 A,B의 시작지점을 포인터로 잡고 크기를 비교하며 새로운 배열에 정렬된 결과값을 담는다. 

예를들어 [12,35]의 배열과 [26,87]의 배열을 하나의 배열로 합치는 과정을 생각해보자.

포인터를 이용하여 12와 26을 비교하여 더 작은값인 12를 새로운 결과값에 담는다.
이제 A배열의 포인터는 35를 가리키고 있다. 35와 26을 비교한다. 이 때 26이 작으므로 26을 새로운배열의 두번째 위치에 담는다. 그리고 바로 이때 inversion count의 갯수를 계산할 수 있다.

어떻게 계산할 수 있을까?

1.합치는 과정에서 각각의 서브배열은 이미 위의 단계에서 정렬을 거쳐 아래로 내려온 배열이기 때문에 정렬된 상태임이 확실하다. 즉 A,B배열의 처음 위치한 원소는 각각의 배열에서 가장 작은 값일것이다.

2.A배열은 B배열보다 순서상으로 앞에 위치하는것이 당연하다. 우리는 원본 배열에 아무런 작업을 하지 않고 그대로 쪼개어 합치는 과정을 했기때문에 아무리 쪼개지고 합쳐지는 과정이 있더라도 각각의 단계에서 A배열은 B배열보다 순서상으로 앞에 위치한다.

위 두 조건을 이용하여 inversion count를 계산할 수 있다.
A,B배열의 원소들을 합치며 정렬할때 만약 B배열의 원소가 A배열의 원소보다 먼저 새로운 결과배열에 담긴다면, B배열이 A배열의 남은 원소들보다 작다는 의미이므로 A배열의 남은 원소의 갯수가 inversion count가 되는것이다.

즉 위의 [12,35] 와 [26,87]배열의 예시에서 먼저 12가 새로운 배열에 담기고, 그 다음 26이 새로운 배열에 담길때 26의 inversion count는 A배열의 남은 원소갯수(1개)가 되는것이다.

이를 코드로 나타내면 (p1는 A배열의 현재 포인터(인덱스)) mid - i + 1이 되는것이다.

void merge(int left, int right)
{
	int mid = (left + right) / 2;

	int i = left;
	int j = mid + 1;
	int k = left;
	while (i <= mid && j <= right)
	{
		if (arr[i].stat >= arr[j].stat)
			temp[k++] = arr[i++];
		else {
			arr[j].inversion += mid - i + 1; //arr[j]의 inversion count
			temp[k++] = arr[j++];
		}
	}

	int tmp = i > mid ? j : i;

	while (k <= right) temp[k++] = arr[tmp++];

	for (int i = left; i <= right; i++) arr[i] = temp[i];
}

void partition(int left, int right)
{
	int mid;
	if (left < right)
	{
		mid = (left + right) / 2;
		partition(left, mid);
		partition(mid + 1, right);
		merge(left, right);
	}
}