BOJ 1517 버블 소트

1 개요

BOJ 1517 버블 소트

• 백준 온라인 저지 1517번 문제
• BOJ 45단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> arr, temp;

long long merge(int left, int mid, int right) {
    int i = left, j = mid, k = left;
    long long inv_count = 0;
    while ((i <= mid - 1) && (j <= right)) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            inv_count += (mid - i);
        }
    }
    while (i <= mid - 1) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (i = left; i <= right; i++) arr[i] = temp[i];
    return inv_count;
}

long long mergeSort(int left, int right) {
    long long inv_count = 0;
    if (right > left) {
        int mid = (left + right) / 2;
        inv_count += mergeSort(left, mid);
        inv_count += mergeSort(mid + 1, right);
        inv_count += merge(left, mid + 1, right);
    }
    return inv_count;
}

int main() {
    cin >> N;
    arr.resize(N);
    temp.resize(N);
    for (int i = 0; i < N; i++) cin >> arr[i];
    cout << mergeSort(0, N - 1);
}