----------------
title : C++ 레퍼런스 - sort 함수 (<algorithm>)
cat_title : sort
ref_title : sort, std::sort
path : /C++ Reference/algorithm
publish_date : 2019-04-10
----------------

##@ cpp-ref-start

#@ sort

`<algorithm>` 에 정의됨

```cpp-formatted
// < 를 이용한 비교 (1)
template <class RandomIt>
void sort(RandomIt first, RandomIt last);

// 비교 함수 (comp) 를 이용한 비교 (2)
template <class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

// Execution policy 를 지정한 경우 (3)
template <class ExecutionPolicy, class RandomIt>
void sort(ExecutionPolicy&& policy, RandomIt first, RandomIt last);

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

범위 (`first` 부터 `last` 전 까지) 내의 원소들을 오름차순으로 정렬합니다. 크기가 같은 원소들의 상대적 위치는 바뀔 수 도 있습니다. 참고로 `first` 와 `last` 는 임의 접근 반복자(`RandomIterator`) 여야 합니다. 따라서 `list` 의 경우 `sort` 함수로 정렬을 수행할 수 없습니다. (`list` 의 반복자는 순차 접근 반복자 입니다.)

* (1) 의 경우 `operator<` 를 이용해서 원소들 간의 크기 비교를 수행합니다.
* (2) 의 경우 인자 두 개를 받아서 크기를 비교하는 함수 `comp` 로 크기 비교를 수행합니다.
* (3), (4) 의 경우 (1), (2) 와 동일하지만, 어떠한 방식으로 실행할 지 지정할 수 있습니다. 참고로 해당 함수가 오버로드 되기 위해서는 `std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>` 가 참이어야 합니다. `ExecutionPolicy` 에 관해서는 해당 문서를 참조해주세요.

### 인자들

* `first, last`	-	정렬을 수행할 원소들의 범위를 가리키는 반복자.
* `policy`	-	어떠한 방식으로 실행 시킬지. `ExecutionPolicy` 참조.
* `comp`	-	인자 두 개를 받는 비교 함수로, 첫 번째 인자가 더 작을 경우 `true` 를 리턴해야 합니다.

`comp` 함수의 모습은 아래와 같다고 보면 됩니다.

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

참고로 인자가 굳이 `const&` 일 필요는 없지만, 함수 내부에서 인자로 받은 원소를 수정하면 안됩니다. 또한 `Type1` 과 `Type2` 는 `RandomIt` 가 가리키는 원소의 타입으로 변환 가능해야만 합니다. (대개 `Type1` 과 `Type2` 는 같습니다.)

### 실행 복잡도

평균적으로 $$O(N \log N)$$ 으로 실행되며 여기서 `N = std::distance(first, last)` 으로 정의됩니다.

### 실행 예제

```cpp-formatted
#include <algorithm>
#include <array>
#include <functional>
#include <iostream>

int main() {
  std::array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

  // operator< 를 사용해 정렬
  std::sort(s.begin(), s.end());
  for (auto a : s) {
    std::cout << a << " ";
  }
  std::cout << '\n';

  // 표준 라이브러리 비교 함수 객체 greater 를 통한 정렬
  std::sort(s.begin(), s.end(), std::greater<int>());
  for (auto a : s) {
    std::cout << a << " ";
  }
  std::cout << '\n';

  // 함수 객체를 이용한 정렬
  struct {
    bool operator()(int a, int b) const { return a < b; }
  } customLess;
  std::sort(s.begin(), s.end(), customLess);
  for (auto a : s) {
    std::cout << a << " ";
  }
  std::cout << '\n';

  // 람다 함수를 이용한 정렬
  std::sort(s.begin(), s.end(), [](int a, int b) { return a > b; });
  for (auto a : s) {
    std::cout << a << " ";
  }
  std::cout << '\n';
}
```

```exec
0 1 2 3 4 5 6 7 8 9 
9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 
9 8 7 6 5 4 3 2 1 0
```

### 참고 자료

* `partial_sort` : 일부 원소들만 정렬한다.
* `stable_sort` : 특정 범위의 원소들을 안정 정렬(stable sort) 한다. 참고로 안정 정렬 이란, 크기가 같은 원소들의 상대적 순서를 바꾸지 않는 정렬을 말합니다.