[세그먼트 트리 단계] 백준 1517번 버블 소트

문제

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

입력

첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다.

출력

첫째 줄에 Swap 횟수를 출력한다

 

 

Counting Inversion과 일맥 상통.

버블 소트로 매 단계에서 swap하는 것이 결국 merge sort에서 inversion 되어있는 인덱스의 수와 같음.

결국 그것이 정렬되면서 swap될 것이기 때문.

#include<iostream> 
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
int arr[500001];
int sorted[500001];
int cnt = 0;
void merge(int left, int mid, int right)
{
	int low = left;
	int k = left;
	int high = mid + 1;
	while (low <= mid && high <= right)
	{
		if (arr[low] <= arr[high])
		{
			sorted[k++] = arr[low++];
		}
		else
		{
			cnt += mid - low + 1;
			sorted[k++] = arr[high++];
		}
	}
	if (low <= mid)
	{
		for (int i = low; i <= mid; i++)
			sorted[k++] = arr[i];
	}
	else
	{
		for (int i = high; i <= right; i++)
			sorted[k++] = arr[i];
	}

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


void merge_sort(int left, int right)
{
	if (left < right)
	{
		int m = (left + right) / 2;
		merge_sort(left, m);
		merge_sort(m + 1, right);
		merge(left, m, right);
	}
}
int main() {
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> arr[i];

	merge_sort(1, N);
	cout << cnt << endl;
}