백준 1517번 버블소트

www.acmicpc.net/problem/1517

1517번: 버블 소트

 

 

 

 

<접근방법>

버블소트는 왼쪽에서 오른쪽으로 이동하며 숫자의 위치를 결정한다.

이를 버블소트 그대로 구현하면 문제의 시간조건에 걸린다.

따라서 머지소트로 정렬하며 이동횟수를 세어준다.

 

왼쪽 배열과 오른쪽 배열을 병합하는 과정에서

오른쪽 배열의 숫자가 선택되어 sorted 배열에 포함된다는 것은

아직 선택되지 않은 왼쪽 배열의 숫자의 갯수만큼 이동한다는 뜻이다.

이를 카운팅한다.

 

---

 

 

 

<코드>

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

int n;
int a[500005];
int b[500005];
long long res;

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 (a[i] <= a[j]) {
			b[k++] = a[i++];
		}
		else {
			res += (mid - i + 1);
			b[k++] = a[j++];
		}
	}

	while (i <= mid) {
		b[k++] = a[i++];
	}
	while (j <= right) {
		b[k++] = a[j++];
	}

	for (int p = left; p <= right; p++) {
		a[p] = b[p];
	}
}

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

	if (left < right) {
		divide(left, mid);
		divide(mid + 1, right);
		merge(left, right);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	divide(1, n);


	cout << res << '\n';

	return 0;
}