불안정 정렬 sort, 안정정력 stable_sort

안정 정렬와 불안정 정렬

지금까지 계속 sort를 써오면서 해당 값에 대해서 순서가 유지되는지 여부를 거의 신경써본적이 없었고 (순서는 당연히 유지되는줄 알았다), 동일한 값에 대해 기존의 순서가 유지되는 정렬을 해본적이 없어서 잘 몰랐는데, sort 함수를 활용한 정렬은 동일한 값에 대해 기존의 순서가 뒤바뀔 수 있다. 

 

아래의 이미지에 잘 나와있는데, stable 같은 경우에는 순서가 확실히 유지되는 반면, not stable 같은 경우에는 같은 값에 대해서 순서가 뒤바뀔 수 있다. 

C++의 sort 와 stable sort

c++의 경우 algorithm 헤더에서 sort 함수와 stable_sort 함수를 둘다 지원하고 있으며, 

sort 함수의 경우 내부적으로 퀵 정렬로,

stable_sort 함수의 경우 병합정렬로 이루어져있다. (sort 함수가 시간은 더 빠르다.)

 

관련된 문제 & 풀이

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

10814번: 나이순 정렬

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

using namespace std;
vector<pair<int, string>> v;

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

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

    int n, tmp;
    string s;

    cin >> n;

    while (n--)
    {
        cin >> tmp >> s;
        v.push_back({tmp, s});
    }

    stable_sort(v.begin(), v.end(), check);

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