[c++] Stable_sort() vs Sort() 함수 차이

1.함수 헤더 파일

#include <algorithm>

2.함수 원형

-sort 함수

// < 를 이용한 비교 (1)
template <class RandomIt>
void sort(RandomIt first, RandomIt last);

// 비교 함수 (comp) 를 이용한 비교 (2)
template <class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

// Execution policy 를 지정한 경우 (3)
template <class ExecutionPolicy, class RandomIt>
void sort(ExecutionPolicy&& policy, RandomIt first, RandomIt last);

template <class ExecutionPolicy, class RandomIt, class Compare>
void sort(ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp);

-stable_sort함수

template <class RandomIt>
void stable_sort(RandomIt first, RandomIt last);  // (1)

template <class RandomIt, class Compare>
void stable_sort(RandomIt first, RandomIt last, Compare comp);  // (2)

// 아래 두 함수는 위와 동일하지만 ExecutionPolicy 를 추가로 받을 수 있다.
template <class ExecutionPolicy, class RandomIt>
void stable_sort(ExecutionPolicy&& policy, RandomIt first, RandomIt last);

template <class ExecutionPolicy, class RandomIt, class Compare>
void stable_sort(ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp);

 

3.return 값(반환 값)

없음

 

4.예제

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

int main(){
	
    vector<int> A = {1, 3, 2, 5, 4, 5, 2, 3};
    
    stable_sort(A.begin(), A.end());   // 1 2 2 3 3 4 5 5   
    stable_sort(A.rbegin(), A.rend()); // 5 5 4 3 3 2 2 1
    
    return 0;
}

 

5. sort vs stable_sort

▶ 기능의 차이

  : 기존에 두 요소가 가지고 있던 순서를 보장하는가 하지 않는가에 따른 기능적 차이가 있다.

sort()	동일한 값의 요소들에 대해, 두 요소가 기존에 가지고 있던 순서를 보장하지 않는다.
stable_sort()	동일한 값의 요소들에 대해, 두 요소가 기존에 가지고 있던 순서를 보장한다.

ex ) {1, 5, 4, 5, 3} → sort : {1, 3, 4, 5, 5 } or { 1, 3, 4, 5,  5 } 

먼저 나오는 파란색 5, 그 다음에 나오는 빨간색 5 는 sort함수에 의해 정렬될 때 순서가 기존의 순서로 보장되지 않는다. 결과에 따라 순서가 바뀔 수 있다.

{1, 5, 4, 5, 3} → stable_sort : {1, 3, 4, 5, 5 } 

기존의 파란색 5가 빨간색 5보단 먼저 온다는 순서가 보장된다. 

 

- 예제

bool cmp(const pair<char, int>& a, const pair<char, int>& b){
    return a.first < b.first;
}

int main(){
    vector<pair<int, int> > vec = { {1, 10}, {5, 3}, {3, 1}, {1, 10} };

    auto address0 = &vec[0];

    std::sort(vec.begin(), vec.end(), cmp); //{1, 10}, {1, 10}, {5, 3}, {3, 1}
    auto address1 = &vec[0];
    auto address2 = &vec[1];

    stable_sort(vec.begin(), vec.end(), cmp); // {1, 10}, {1, 10}, {5, 3}, {3, 1}
    auto address3 = &vec[0];
    auto address4 = &vec[1];
    return 0;
}

sort, stable_sort 둘다 결과는 동일하게 나온다. 

첫번째 인덱스인 {1, 10} 요소가 먼저 나오는지 체크를 해야한다.

주소값을 이용하여 비교하였다.

address3이 기존 순서인 address0과 같다면 순서 보장이 된 것이다.

address1은 기존 순서인 address0과 같을 수도 다를 수도 있다. sort함수는 순서를 보장하지 않기 때문이다.

 

▶ 내부 정렬 알고리즘 차이

sort()	Quick
stable_sort()	Merge Sort

 

▶ 시간복잡도 차이

sort()	평균적으로 O(N log N)O(NlogN) 으로 실행되며 여기서 N = std::distance(first, last) 으로 정의됩니다.
stable_sort()	N 을 전달하는 원소의 개수 (N = std::distance(first, last)) 라고 할 때, O(N (log N)^2)O(N(logN)2) 이다. 만일 추가적인 메모리를 사용할 수 있다면 복잡도는 O(N\log N)O(NlogN) 으로 줄어든다. 참고로 함수 내부적으로 정렬해야 할 컨테이너와 같은 크기의 메모리를 처음에 할당하려고 한다. 만일 메모리 할당이 성공 한다면 O(Nlog N)O(NlogN) 의 속도로 실행이 될 것이고, 실패한다면 조금 느린 버전의 알고리즘이 사용되어 O(N (log N)^2)O(N(logN)2) 으로 정렬된다.