----------------
title : C++ 레퍼런스 - std::stable_sort (<algorithm>)
cat_title : stable_sort
ref_title : std::stable_sort, stable_sort
path : /C++ Reference/algorithm
publish_date : 2020-12-06
----------------

##@ cpp-ref-start

#@ stable_sort

`<algorithm>` 에 정의됨

```cpp-formatted
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)

// 아래 두 함수는 위와 동일하지만 ExecutionPolicy 를 추가로 받을 수 있다.
template <class ExecutionPolicy, class RandomIt>
void stable_sort(ExecutionPolicy&& policy, RandomIt first, RandomIt last);

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

**범위 내의 원소들의 오름 차순 (크기가 작은 것에서 큰 순으로) 안정 정렬을 수행한다** 참고로 안정 정렬 이란, 크개가 같은 원소들의 상대적 위치가 바뀌지 않는 정렬이다.

예를 들어서 (3, a), (2, b), (2, c), (1, d) 라는 데이터가 있을 때 정수값으로 안정 정렬을 수행한다면 반드시 (1, d), (2, b), (2, c), (3, a) 가 되지, (1, d), (2, c), (2, b), (3, a) 는 될 수 없다. 왜냐하면 이전에 (2, b) 가 (2, c) 앞에 있었기 때문이다.

(1) 번 함수의 경우 `operator<` 를 사용해서 크기 비교를 수행한다.
(2) 번 함수의 경우 비교 함수인 `comp` 를 이용해서 크기 비교를 수행한다.

밑의 두 함수의 경우 추가적으로 실행 방식을 첫 번째 인자로 전달할 수 있는데, 전달하는 `policy` 의 경우 반드시 `std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` 를 만족해야 한다.

### 인자들

* `first`, `last`: 생성된 값을 대입할 원소들의 범위를 나타낸다.
* `policy` : 사용할 실행 방식
* `comp` : 두 원소를 비교할 함수로 아래와 같은 꼴 이어야 한다.

```cpp
 bool cmp(const Type1 &a, const Type2 &b);
```

이 때 함수의 인자 타입은 반드시 `const&` 일 필요는 없으나, 함수안에선 반드시 전달받은 인자를 변경해서는 안된다. 또한 전달하는 인자들은 반드시 `Type1` 과 `Type2` 로 치환 가능해야만 한다.

### 리턴값

없음

### 시간 복잡도

N 을 전달하는 원소의 개수 (`N = std::distance(first, last)`) 라고 할 때, $$O(N (\log N)^2)$$ 이다. 만일 추가적인 메모리를 사용할 수 있다면 복잡도는 $$O(N\log N)$$ 으로 줄어든다. 

참고로 함수 내부적으로 정렬해야 할 컨테이너와 같은 크기의 메모리를 처음에 할당하려고 한다. 만일 메모리 할당이 성공 한다면 $$O(N\log N)$$ 의 속도로 실행이 될 것이고, 실패한다면 조금 느린 버전의 알고리즘이 사용되어 $$O(N (\log N)^2)$$ 으로 정렬된다.

### 구현 예시

* [libc++](https://github.com/llvm-mirror/libcxx/blob/a12cb9d211019d99b5875b6d8034617cbc24c2cc/include/algorithm#L4696)

### 실행 예제

```cpp-formatted
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Employee {
  int age;
  std::string name;  // Does not participate in comparisons
};

bool operator<(const Employee& lhs, const Employee& rhs) {
  return lhs.age < rhs.age;
}

int main() {
  std::vector<Employee> v = {
    {108, "Zaphod"},
    {32, "Arthur"},
    {108, "Ford"},
  };

  std::stable_sort(v.begin(), v.end());

  for (const Employee& e : v) std::cout << e.age << ", " << e.name << '\n';
}
```

```exec
32, Arthur
108, Zaphod
108, Ford
```

### 참고 자료

* `partial_sort` : 범위 안의 첫 N 개의 원소들을 정렬한다.
* `sort` : 범위 안의 원소들을 오름차순으로 정렬한다.