stable_sort()

만약에 들어온 순서대로 정렬하고 싶으면? sort()가 아니라 stable_sort()를 써야 한다.

 

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

using namespace std;

int main()
{
    // pair의 첫 번째 요소는 정렬할 값, 두 번째 요소는 원래 인덱스
    vector<pair<int, int>> pairs = {{2, 1}, {4, 2}, {5, 3}, {5, 4}, {3, 5}};
    
    cout << "Original: ";
    
    for (const auto& p : pairs)
    {
        cout << "(" << p.first << ", " << p.second << ") ";
    }
    
    cout << '\n';
    
    sort(pairs.begin(), pairs.end());
    
    cout << "Sorted sort: ";
    for (const auto& p : pairs)
    {
        cout << "(" << p.first << ", " << p.second<< ") ";
    }
    
    cout << '\n';
    
    // 원본 데이터로 초기화
    pairs = {{2, 1}, {4, 2}, {5, 3}, {5, 4}, {3, 5}};
    
    // stable_sort 사용
    stable_sort(pairs.begin(), paris.end());
    
    cout << "Sorted stable_sort: ";
    
    for (const auto& p : pairs)
    {
        cout << "(" << p.first << ", " << p.second << ") ";
    }
    
    cout << '\n';
    
    return 0;
}

 

결과물을 보자

 

first 기준으로 잘 정렬이 되었고 sort와 stable_sort의 값이 둘 다 똑같았다.

 

그러나 sort()의 경우 마지막 두번째 부분 보면 (5, 3), (5, 4) 이렇게 나올수도 있고, (5, 4), (5, 3) 이렇게 나올 수도 있다는 것

stable_sort()는 무조건 기존의 순서를 지켜준다.

그 러 니 까

first가 같은 값일 경우 (5, 3)이 (5, 4)보다 원래 앞에 있었으므로 (5, 3), (5, 4) 이렇게 나오게 된다는 것이다.

 

 

결론은 그렇다

 

sort와 stable_sort의 차이는

sort 함수는 불안정 정렬 알고리즘을 사용한다.

그러니까 같은 값을 가진 요소들의 들어온 순서를 정렬후에 보존하지 않는다는거다.

 

stable_sort 함수는 안정 정렬 알고리즘을 사용한다.

같은 값을 가진 요소들의 들어온 순서를 정렬후에도 보존한다.

 

 

아유 쓰기 어렵다 어려워