algorithm_stable_sort
algorithm_stable_sort (안정적 정렬)
std::stable_sort는 대상 범위 [first, last)의 요소들을 정렬하고, 동등한 요소들의 상대적 순서를 보존해요. std::sort와 달리 안정적이에요.
출처: cppreference
본문
std::stable_sort는 대상 범위 [first, last)의 요소들을 정렬해요. 동등한 요소들의 순서가 보존되는 것이 보장돼요. <algorithm> 헤더에 정의되어 있어요.
template< class RandomIt >
void stable_sort( RandomIt first, RandomIt last );
template< class RandomIt, class Compare >
void stable_sort( RandomIt first, RandomIt last, Compare comp );
- 1번 오버로드 — 요소를
operator<(즉std::less{})를 기준으로 정렬해요. - 2번 오버로드 — 요소를 비교 함수
comp를 기준으로 정렬해요. - 병렬 실행 정책을 받는 오버로드도 있어요.
복잡도 (Complexity)
N을 std::distance(first, last)라고 하면 적절한 추가 메모리가 있으면 𝓞(N·log N)번의 비교가 필요하고, 추가 메모리가 없으면 𝓞(N·log²N)번의 비교가 필요해요.
예제 (Example)
#include <algorithm>
#include <iostream>
#include <vector>
struct Item { int key; int order; };
int main()
{
std::vector<Item> v{{2, 1}, {1, 2}, {2, 3}, {1, 4}};
std::stable_sort(v.begin(), v.end(),
[](const Item& a, const Item& b) { return a.key < b.key; });
for (auto& it : v)
std::cout << it.key << ':' << it.order << ' ';
std::cout << '\n';
}
출력 (동등한 키의 순서 보존):
1:2 1:4 2:1 2:3