[C++/lib:algorithm] stable_sort()(안정적으로 정렬)

sort()의 문제점

최근 백준 문제를 풀던 중, pair로 담은 vector에서 이중 정렬을 compare() 를 구현하여 sort() 인자로 넣는 것 까진 잘 이해 하면서 풀었다.

 

하지만, pair에서 정렬 기준을 2개를 잡는 것이 아닌,

 

1개만 잡고 하면 나머지 다른 원소는 입력된 순서로 정렬 되는 것이 아닌 ,

 

무작위로 정렬이 된다.

 

예를 들어보자.

 

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

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

using namespace std;

bool comp(pair<int, string> a, pair<int, string> b) { return a.first < b.first; }

int main() {
    int T;
    int age;
    string name;
    vector<pair<int, string>> skdltns;
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> age >> name;
        skdltns.push_back(make_pair(age, name));
    }
    sort(skdltns.begin(), skdltns.end(), comp);
    for (int i = 0; i < T; i++) cout << skdltns[i].first << " " << skdltns[i].second << '\n';

    return 0;
}

 

다음은 나이,이름을 받고 나이순으로 정렬하는 백준 문제이다.

 

입력은 다음과 같다.

3
21 Junkyu
21 Dohyun
20 Sunyoung

 

이 입력값에 대한 출력값은 백준 페이지에 나온 값과 동일하지만 다를 경우는 그렇지 않다.

 

<출력>

20 Sunyoung
21 Junkyu
21 Dohyun

 

이것은 백준에 나와있는 출력값과 동일하다.

 

하지만 sort() 만으로는 나이가 같을때

21 Junkyu
21 Dohyun

21 Dohyun
21 Junkyu

 

둘 중 어느 것으로 정해주는지는 알 수 없고 랜덤에 가깝다고 볼 수 있다.

 

stable_sort() 개념

위와 같은 문제점을 개선해주도록 stable_sort()를 사용할 수 있다.

 

stable_sort()는 말 그대로 안정적으로 정렬해주는 것이다.

 

만약 위와 같은 코드에서 sort() → stable_sort()로 바꿔주면,

 

정렬 기준을 정하지 않은 "name" 변수에 대해서는 들어온 순서대로 아무 조작없이 정렬해주는 것이다.

 

즉, 입력값인

21 Junkyu
21 Dohyun

에 대해 같은 나이에 대해서는 J..와 D..의 순서를 지켜준다는 것이다.

 

이 원리와 구조는 지금 내가 별로 궁금하지 않기 때문에 찾아보지 않았다.

 

stable한 sort()를 직접 구현하는 것도 중요하지만,

 

저 문제는 stable_sort() 라는 lib가있다는 것을 알려주고 싶었던 것이 아닐까.