sort

<algorithm> 에 정의됨

// < 를 이용한 비교 (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 함수의 모습은 아래와 같다고 보면 됩니다.

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

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

실행 복잡도

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

실행 예제

#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';
}

실행 결과

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) 한다. 참고로 안정 정렬 이란, 크기가 같은 원소들의 상대적 순서를 바꾸지 않는 정렬을 말합니다.

댓글이 2 개 있습니다!

강좌에 관련 없이 궁금한 내용은 여기를 사용해주세요

다음으로 로그인

또는 직접 입력하세요 (댓글 수정시 비밀번호가 필요합니다)

댓글 달기

댓글을 불러오는 중입니다..