[C++ stable_sort] stable_sort

최근에 코딩 테스트 문제를 풀다가 stable_sort 함수에 대해서 알게되었습니다.
알게된 내용을 잊지않기 위해 정리한 내용입니다.

잘못된 부분이 있다면 지적부탁드립니다!

 

std::sort

stable_sort의 내용을 언급하기 전에 대표적인 정렬 함수 sort 먼저 살펴보도록 하겠습니다.

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

using namespace std;

int main(void) {
    vector<pair<int, int>> v = {{5,1}, {1,2}, {3,9}, {2, 7}, {4, 3}, {1,5}};
    cout << "sort 함수 사용 전" << '\n';
    for(pair<int,int> element : v) {
        cout << element.first << ' ' << element.second << '\n';
    }
    cout << '\n';

    sort(v.begin(), v.end());
    cout << "sort 함수 사용 후" << '\n';
    for(pair<int, int> element : v) {
        cout << element.first << ' ' << element.second << '\n';
    }
    cout << '\n';
}

초기 배열의 상태입니다.

 

 

sort 함수를 사용하여 첫번째 원소를 기준으로 오름 차순 정렬한다면 배열의 상태는 아래와 같이 변경될 수 있습니다.

 

 

정렬 후 같은 중복된 원소 1은 정렬 순서가 처음 순서와 같지 않을 수 있습니다.
즉, 동일한 값에 대해 불안정한 정렬이라고 이야기 할 수 있습니다.

 

 

std::stable_sort

 

위 sort 함수와는 다르게 stable_sort 함수는 동일한 값에 대해 순서가 정렬 전과 같이 그대로 유지되는 안정 정렬입니다.

 

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

using namespace std;

int main(void) {
    vector<pair<int, int>> v = {{5,1}, {1,2}, {3,9}, {2, 7}, {4, 3}, {1,5}};
    cout << "stable_sort 함수 사용 전" << '\n';
    for(pair<int,int> element : v) {
        cout << element.first << ' ' << element.second << '\n';
    }
    cout << '\n';

    stable_sort(v.begin(), v.end());
    cout << "stable_sort 함수 사용 후" << '\n';
    for(pair<int, int> element : v) {
        cout << element.first << ' ' << element.second << '\n';
    }
    cout << '\n';
}

 

 

결과와 같이 동일한 값에 대해 이전 정렬 순서와 동일하게 정렬 순서를 유지합니다.

 

 

시간 복잡도 차이

 

sort 함수의 경우 퀵 정렬로 처리하고, stable_sort 함수의 경우 병합 정렬로 처리합니다.

보통 sort 함수가 stable_sort 함수보다 빠르다고 합니다.

 

 

(참고)

std::stable_sort - cppreference.com