백준 10814: 나이순 정렬 (병합 정렬)

폰노이만...

https://www.acmicpc.net/problem/10814

병합 정렬은 무한 츠쿠요미 함수를 이용한 정렬 방식이다.

1. 쪼갤 수 있는 만큼 쪼개면서 배열을 쪼갠다.

(실제로 쪼개는건 아니고, 2개의 피봇으로 시작과 끝의 구분을 두었다.)

2. 그러면 배열의 시작과 끝이 같은 곳을 보거나 그럴텐데, 그건 건너뛴다.

3. start와 end가 같은 재귀함수(39 : start < end)는 건너뛰고, start와 end가 1차이나는 재귀는 병합한다.

4. 병합은 그 대진표 형식으로 정렬시킨다. 솔직히 이거 설명만 들으면 아~ 하는데 막상 코드 첨보면 이게 뭔가 싶다.

5. start와 end가 1차이나는 재귀 배열은 서로 정렬이 되어서 합쳐지고, 이제 start와 end가 2차이나는 배열이 남는다.

6. 이제 1:1이 아니라 2:2 태그매치다. 누가 더 숫자가 낮은지 겨뤄서 다시 정렬한다.

7. 4:4... 8:8... 올라가면서 계속 정렬한다.

8. 홀수인 경우? 하나는 겨뤄봄직한 상대가 없어서 부전승을 치지만, 다음 매치에서 결국 정렬당한다.

9. 폰노이만....

#include <iostream>
#include <string>
#include <vector>
 
struct member
{
    int age = 0;
    std::string name;
};
 
std::vector<member> tmpVec;
 
void _merge(std::vector<member>& members, int start, int end)
{
    int mid = (start + end) / 2;
    int i = start;
    int j = mid + 1;
    int k = start;
 
    while (i <= mid && j <= end)
    {
        if (members[i].age <= members[j].age)
            tmpVec[k++] = members[i++];
        else
            tmpVec[k++] = members[j++];
    }
 
    int tmp = i > mid ? j : i;
 
    while (k <= end)
        tmpVec[k++] = members[tmp++];
 
    for (int i = start; i < k; ++i)
        members[i] = tmpVec[i];
}
 
void _mergesort(std::vector<member>& members, int start, int end)
{
    if (start < end)
    {
        int m = (start + end) / 2;
        _mergesort(members, start, m);
        _mergesort(members, m + 1, end);
        _merge(members, start, end);
    }
}
 
int main()
{
    std::ios::sync_with_stdio(false);
    std::cout.tie(0);
    std::cin.tie(NULL);
    std::ios_base::sync_with_stdio(false);
    int N;
    std::cin >> N;
    std::vector<member> members;
    members.reserve(N);
    tmpVec.reserve(N);
    member input;
    for(int i = 0; i < N; ++i)
    {
        std::cin >> input.age >> input.name;
        members.push_back(input);
        tmpVec.push_back(input);
    }
    _mergesort(members, 0, N - 1);
    for (auto it : members)
        std::cout << it.age << ' ' << it.name << '\n';
    return 0;
}

자매품.

stable_sort 함수

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
bool cmp(std::pair<int, std::string> first, std::pair<int, std::string> second)
{
    if (first.first < second.first)
        return true;
    else
        return false;
}
 
int main()
{
    int N;
    std::cin >> N;
 
    std::vector<std::pair<int, std::string>> members;
    members.reserve(N);
 
    std::pair<int, std::string> input;
    for(int i = 0; i < N; ++i)
    {
        std::cin >> input.first >> input.second;
        members.push_back(input);
    }
 
    stable_sort(members.begin(), members.end(), cmp);
 
    for (auto it : members)
        std::cout << it.first << ' ' << it.second << '\n';
    return 0;
}

비교함수만 만들면 되는 간단한 문제이지만 그래서는 공부라고 할 수 없다

암기...암기가 최고야...