'C++' std::sort, std::stable_sort

sort

template<class RandomIt>
void sort(RandomIt first, RandomIt last); // constexpr since C++20

template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIT last, Compare comp); // constexpr since C++20

C++17 ~

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

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

: 범위 내의 요소를 정렬(문자열은 사전순)하며, comp를 제공하지 않으면 오름차순으로 정렬합니다.

stable_sort

template<class RandomIt>
void stable_sort(RandomIt first, RandomIt last); // constexpr since C++26

template<class RandomIt, class Compare>
void stable_sort(RandomIt first, RandomIT last, Compare comp); // constexpr since C++26

C++17 ~

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

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

: sort와 마찬가지로 범위 내의 요소를 정렬하지만 동일한 값들에 대해서 원래 순서를 보장합니다.

stable_sort는 동일한 값들의 순서를 유지해야 할 때 사용합니다.
일반적으로 sort보다 더 많은 메모리를 사용하고, 더 느립니다.

• first : 정렬을 시작할 첫 번째 요소를 가리키는 임의 접근 반복자
• last : 정렬을 종료할 마지막 번째 요소의 다음 위치를 가리키는 임의 접근 반복자
• comp : 정렬 기준이 정의된 비교 함수 또는 함수 객체
• policy : 실행 정책

실행 정책은 std::execution 헤더에 포함되어있습니다.

• execution::seq : 순차 실행 (기본 값)
• execution::par : 병렬 실행 (멀티코어 시스템에서 작업이 병렬로 수행됩니다.)
• execution::par_unseq : 병렬 및 비순차 실행

<example> | sort

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

using namespace std;

int main() {
	vector<int> vec = {5, 8, 2, 1, 6};
    
    sort(vec.begin(), vec.end());
    
    cout << "Ascending order : ";
    
    for (const int & num : vec) {
    	cout << num << " "; 
    }
    
    cout << endl;
    
    cout << "Descending order : ";
    
    sort(vec.begin(), vec.end(), [](int &x, int &y) { return x > y; });
    
    for (const int & num : vec) {
    	cout << num << " "; 
    }

	return 0;
}

결과값

<example> | stable_sort

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

using namespace std;

int main() {

	vector<pair<int, int>> data = {{10, 1}, {20, 2}, {30, 3}, {20, 4}, {10, 5}};

	stable_sort(data.begin(), data.end(), 
    [](const pair<int, char>& a, const pair<int, char>& b) {return a.first < b.first;});

	for (const auto& i : data) {
    	cout << i.first << " | existing order : " << i.second << "\n";
	}

	return 0;
}

결과값

sort로 했을 때도 동일한 결과가 나왔지만, 정렬하고자 하는 데이터의 크기가 커질수록 sort와 stable_sort는 확연히 다른 결과를 내놓을 수 있습니다.
예를 들어 위의 코드에서 stable_sort를 sort로 바꿨을 때 이런 결과가 나올 수 있습니다.
10 | exisiting order : 5
10 | exisiting order : 1
20 | exisiting order : 4
20 | exisiting order : 2
30 | exisiting order : 3