[1517] 버블 소트

문제 출처 : https://www.acmicpc.net/problem/1517

분류 : 정렬

백준 1517 버블 소트

NlogN 안에 swap수를 구하자

---

구현 포인트

1) Merge sort를 이용하여 swap을 구한다. (O(NlogN))

2) long long으로 답을 기록한다.

일반적인 버블소트나 flagged한 방법을 써도 N이 크므로 시간초과가 난다. 

생각보다 방법을 떠올리기 쉽지 않아서 기록을 남기기로 하였다.

핵심은 Merge를 통해 NlogN으로 time을 줄이는데에 있다.

절반씩 나누어 정렬을 하는데, 그 안에서 Bubble Sort로 정렬하는 것이 아니라 Merge sort를 하면서

비교 인덱스를 이용하여 swap수를 바로 구해준다. (아래 코드의 line 21)

이 과정은 O(1) 시간이 걸리고, Merge sort는 각 함수 당 최대 n-1번 비교하므로

결국 time complexity가 O(NlogN)이 나와 주어진 시간내에 해결이 가능하다.

코드는 아래와 같다.

#include<iostream>
#include<vector>
using namespace std;
 
long long ans = 0;
 
void mergeBubble(vector<int>&a, int s, int d) {
    if (s == d) return;
    int mid = (s + d) / 2;
    vector<int> tmp;
    mergeBubble(a, s, mid);
    mergeBubble(a, mid + 1, d);
    int i = s, j = mid + 1;
    while (i <= mid && j <= d) {
        if (a[i] <= a[j]) {
            tmp.push_back(a[i]);
            i++;
        }
        else {
            tmp.push_back(a[j]);
            ans += (mid + 1 - i);
            j++;
        }
    }
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= d) tmp.push_back(a[j++]);
    for (int i = s, j = 0; i <= d; i++, j++) {
        a[i] = tmp[j];
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    mergeBubble(a, 0, a.size() - 1);
    printf("%lld\n", ans);
}