ranges::stable_sort
ranges::stable_sort (안정 정렬 — ranges)
같은 값을 가진 원소들의 상대 순서를 유지하며 정렬하는 ranges 버전 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
std::ranges::stable_sort는 범위를 비감소 순서로 정렬하되, 동등한 원소 사이의 원래 순서를 보존해요.
namespace std::ranges {
template< std::random_access_iterator I, std::sentinel_for<I> S,
class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
constexpr I stable_sort( I first, S last, Comp comp = {}, Proj proj = {} );
}
- 복잡도: 충분한 임시 메모리가 있으면
N·log²N비교, 아니면N·log²N·log N. ranges::sort보다 비싸지만 안정적이에요.
struct Item { int key; int id; };
// key 기준 정렬 시 같은 key면 id 순서 유지
std::ranges::stable_sort(items, {}, &Item::key);
동등한 요소의 원래 순서를 보존해야 하는 경우(예: 2차 정렬 유지)에 써요.