StableSort

지정된 범위에 있는 요소들을 오름차순 또는 이항 술어에 의해 지정된 순서 기준에 따라 정열하고 동일한 요소들의 상대적 순서는 유지합니다.

template <class Bi>
void StableSort (
    Bi                  first,
    Bi                  last
);

template <class Bi, class BinPred>
void StableSort (
    Bi                  first,
    Bi                  last,
    BinPred             cmp
);

Template 파라미터

Bi

양방향 반복자입니다.

BinPred

이항 술어(Binary predicate)입니다.

파라미터

first

정렬될 범위의 1번째 요소의 위치를 설명하는 양방향 반복자입니다.

last

정렬될 범위의 마지막 직전 요소의 위치를 설명하는 양방향 반복자입니다.

cmp

순서상으로 연속적인 요소들에 의해 만족되는 비교 기준을 정의하는 사용자 정의 술어 함수 객체입니다. 이항 술어(binary predicate)는 2개의 인자를 취하며 만족할 때에는 true를, 만족하지 않을 때에는 false를 리턴합니다.

설명

StableSort는 Sort와 매우 비슷합니다: 이것은 [first, last)의 요소들을 오름차순으로 정렬합니다. 즉, [first, last)에서 i와 j가 유효한 반복자들이라면, i는 j보다 앞설 경우 *j는 *i보다 작지 않습니다. StableSort는 Sort와 2가지 면에서 다릅니다. 첫째, StableSort는 Sort와 다른 런타임 복잡도를 갖는 알고리즘을 사용합니다. 둘째, 이름으로 유추할 수 있듯이 StableSort는 안정적입니다: 이것은 같은 요소들의 상대적인 순서를 보존합니다. 즉, x와 y가 [first, last)의 요소들이라면 x가 y보다 앞설 경우 그리고 두 요소들이 같을 경우 (x < y나 y < x도 아님) StableSort의 후조건은 여전히 x가 y보다 앞선다는 것입니다. StableSort의 2가지 버전들은 어떤 요소가 다른 요소보다 작은지 여부를 정의하는 방법에서 차이가 있습니다. 1번째 버전은 operator<를 사용하여 객체들을 비교하고, 2번째 버전은 술어 cmp를 사용하여 객체들을 비교합니다.

참고사항

알고리즘