[백준] 1517번 | 버블 소트 | C++

---

문제 링크: https://www.acmicpc.net/problem/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 횟수를 출력한다.

---

내 풀이

버블 소팅을 사용하면 시간이 너무 오래 걸리니 머지 소팅(merge sort)을 사용해서 정렬하며 각 숫자가 얼마나 이동했는지를 계산한다.

---

코드

#include <iostream>
#define len 500001
using namespace std;

int N;
long long arr[len], arr2[len], result;

long long func(int start, int end) {
	if (start == end)
		return 0;

	int i, j, idx, mid;
	mid = (start + end) / 2;	i = start;	j = mid + 1;	idx = 0;

	result = func(start, mid) + func(mid + 1, end);

	while (i <= mid || j <= end) {
		if (i <= mid && (j > end || arr[i] <= arr[j]))
			arr2[idx++] = arr[i++];
		else {
			result += (mid - i + 1);
			arr2[idx++] = arr[j++];
		}
	}

	for (int k = start; k <= end; k++)
		arr[k] = arr2[k - start];

	return result;
}

int main() {
	scanf("%d", &N);

	for (int n = 0; n < N; n++)
		scanf("%lld", &arr[n]);

	result = func(0, N - 1);

	printf("%lld", result);

	return 0;
}