[Platinum / 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 횟수를 출력한다

💻 코드 (C++)

#include <iostream>
#include <vector>
using namespace std;
vector<int> arr;
long long ans;

void merge(int p, int q, int r) {
	int left = q - p + 1; // p ~ q 크기
	int right = r - q; // q+1 ~ n 크기
	vector<int> L(left);
	vector<int> R(right);
	// 배열 복사하기
	for(int i = 0; i < left; i++) L[i] = arr[p+i];
	for(int j = 0; j < right; j++) R[j] = arr[q+j+1];
	
	int i = 0, j = 0, k = p; // k는 채울 A 위치
	while(i < left && j < right) { // 배열에 병합 안된 원소가 있으면 arr 처음부터 채우기
        if(L[i] <= R[j]) {
			arr[k] = L[i]; i++;
		} else {
			arr[k] = R[j]; j++;
            ans += (left - i);
		}
		k++;
	}
	// 둘 중 하나 끝내고 나머지 복사
	while(i < left) {
		arr[k] = L[i];
		i++; k++; 
	}
	while(j < right) {
		arr[k] = R[j];
		j++; k++; 
	}
}

void merge_sort(int p, int r) {
	if(p >= r) // 0 or 원소 1개
		return;
	int q = (p+r)/2;
	merge_sort(p, q);
	merge_sort(q+1, r);
	merge(p, q, r);
}		 

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
    int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}
	merge_sort(0, n-1);
	cout << ans;
	return 0;
}