[2751] 수 정렬하기 2 (C++)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

static vector<int> A;
static vector<int> result;

void merge(int s, int e);
void partition(int s, int e);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; cin >> n;
    A.resize(n);
    result.resize(n);

    for (int i = 0; i < n; i++)
        cin >> A[i];

    partition(0, n - 1);

    for (int i = 0; i < n; i++)
        cout << A[i] << "\n";

    return 0;
}

void partition(int s, int e)
{
    int mid;

    if (s < e) {
        mid = (s + e) / 2;
        partition(s, mid);
        partition(mid + 1, e);
        merge(s, e);
    }
}

void merge(int s, int e)
{
    int mid = (s + e) / 2;
    int i = s;
    int j = mid + 1;
    int k = s;

    while (i <= mid && j <= e) {
        if (A[i] > A[j])
            result[k++] = A[j++];
        else
            result[k++] = A[i++];
    }

    if (i > mid) {
        while (j <= e)
            result[k++] = A[j++];
    }
    else {
        while (i <= mid)
            result[k++] = A[i++];
    }

    for (int a = s; a <= e; a++)
        A[a] = result[a];
}

 

1. vector A와 result를 크기 n으로 초기화

2. 병합 정렬 알고리즘을 사용

3. partition 함수에서 A를 나누어지지 않을 때까지 나눔

4. merge에서 나눠진 vector의 가장 앞 항부터 차례로 비교하여 result에 정렬

5. result에 정리된 값들을 A에 복사 후 출력