sort

C++ STL 에서 제공하는 sort() 함수는 Quick 정렬의 시작복잡도가 최악의 경우 O(n^2)인 것을 보안하기 위해 Intro 정렬의 변형된 방식을 사용한다. 이때 Intro 정렬은 Quick 정렬과 Heap 정렬을 섞은 방식으로 C++의 sort 함수는 여기에 Insertion 정렬까지 섞어서 사용한다. 시간복잡도는 O(nlogn)을 가진다.

여기서 중요한 점은 sort 함수는 Quick 정렬을 사용하기 때문에 서로 같은 값을 가진 원소들의 순서가 처음 상태와 같지 않을 수 있다. 즉, 불안정(unstable) 한 정렬이 된다.

예시를 들어보면
5 2 2 1 4 의 원소를 가진 배열을 정렬한다고 했을 때
같은 값을 가지는 경우에 원소의 순서에 대한 조건이 따로 없다면

1 2 2 4 5
1 2 2 4 5

로 먼저 들어온 원소에 대한 순서를 유지한 채로 정렬될 수도 혹은 바뀐 채로 정렬될 수도 있다는 것이다.

따라서 같은 값을 가지는 경우에 먼저 들어온 원소에 대한 조건을 이용하는 문제일 경우

• 원소들의 순서를 가지는 변수를 추가하거나
• C++ STL 에서 제공하는 또 다른 함수인 stable_sort() 함수를 사용한다.

stable_sort

평균적인 시간복잡도는 sort() 함수와 같지만 stable_sort() 함수는 Quick 정렬 대신 Merge 정렬을 통해 정렬을 수행한다. 이때 Merge 정렬은 같은 값을 갖는 원소들의 순서를 보장해주기 때문에 안정한 정렬이 된다.

구현 예시

https://www.acmicpc.net/problem/10814
백준 10814번 나이순 정렬을 통해 stable_sort의 예시를 찾을 수 있다.
문제 설명은 나이에 따라 내림차순으로 정렬하게 되는데 만약 같은 나이를 가진 경우 먼저 들어온 원소의 순서대로 정렬을 수행하여 출력하는 것이다.
따라서 sort 함수가 아닌 stable_sort 함수를 사용하였다.

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

using namespace std;

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    int a;
    string str;
    vector<pair<int, string>> my_v;
    
    cin >> n;

    for(int i = 0; i < n; i++)
    {
        cin >> a >> str;
        my_v.push_back(make_pair(a,str));
    }

    stable_sort(my_v.begin(), my_v.end(),
    [](auto a, auto b)
    {
        return a.first < b.first;
    }
    );

    for(int i = 0; i < my_v.size(); i++)
    {
        cout << my_v[i].first << " " << my_v[i].second << "\n";
    }

    return 0;
}