stable_sort
stable_sort (안정 정렬)
같은 값을 가진 원소들의 상대 순서를 유지하며 정렬하는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
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)
- 복잡도: 충분한 임시 메모리가 있으면
N·log²N비교, 아니면N·log²N·log N. sort보다 비싸지만 안정적이에요.
// key 기준 정렬 시 같은 key면 원래 id 순서 유지
std::stable_sort(items.begin(), items.end(),
[](const Item& a, const Item& b){ return a.key < b.key; });
동등한 요소의 원래 순서를 보존해야 하는 경우(예: 2차 정렬 유지)에 sort 대신 써요.