[C++] std::sort와 커스텀 비교 함수로 정렬하기

• TL;DR
• std::sort
  • 특징
  • 오버로딩
    • 1. std::sort(first, last);
    • 2. std::sort(policy, first, last);
    • 3. std::sort(first, last, comp);
    • 4. std::sort(policy, first, last, comp);
• first, last
  • 예시
• 비교 함수(Comparison Function)
  • 비교 함수 작성하기
  • 비교 함수 예시
  • 명명된 요구 사항: $Compare$Compare
• 참고

• std::vector<T> v 비내림차순(≒ 오름차순)으로 정렬하기
  • std::sort(v.begin(), v.end());
• 비오름차순(≒ 내림차순)으로 정렬하기
  • std::sort(v.begin(), v.end(), std::greater<자료형>());
• 커스텀 비교 함수 사용하기
  • std::sort(v.begin(), v.end(), comp)
  • bool comp(int a, int b) { return a > b; } (비오름차순 정렬인 경우)
• arr[N] 정렬하기
  • std::sort(arr, arr + N);

• C++이라면 <algorithm> 헤더 안에 sort 함수가 정의되어 편하게 정렬할 수 있다.
  • sort 함수의 명세는 cppreference에서 찾아볼 수 있다.

특징

잊지 말아야 할 sort 함수의 특징들이 있다.

• [first, last) 구간의 요소들을 non-descending order, 즉 비내림차순으로 정렬된다.
• 이 과정에서 값이 같은 요소들 사이의 순서는 보장되지 않는다(= unstable하다).
• 시간복잡도는 $O(N\times log(N\left)\right)$O(N×log(N))이다.
  • $N$N은 last - first(요소들의 갯수)

오버로딩

• sort 함수는 4가지 오버로딩을 가진다.

1. std::sort(first, last);

template< class RandomIt >  
void sort( RandomIt first, RandomIt last );

• 가장 기본적인 비내림차순 정렬 방법이다.
• C++20 이전까지는 < 연산자, C++부터는 std::less{}를 기준으로 요소를 정렬한다.
  • < 또는 less를 사용하기 때문에 작은 요소가 앞으로, 큰 요소가 뒤로 온다.

2. std::sort(policy, first, last);

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

• 1번과 같지만, policy 방식을 적용하여 정렬한다.
  • execution policy란 C++에서 병렬 알고리즘을 제어하기 위한 기능인데, 자세한 내용은 cppreference에서 확인할 수 있다.

3. std::sort(first, last, comp);

template< class RandomIt, class Compare >  
void sort( RandomIt first, RandomIt last, Compare comp );

• comp 함수를 기준으로 요소를 정렬한다.
  • comp 함수의 자세한 설명은 아래쪽 비교 함수를 참고하자!

4. std::sort(policy, first, last, comp);

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

• 3번과 같지만, policy 방식을 적용하여 정렬한다.

• first, last는 정렬할 요소들의 범위를 나타낸다.
• 위 오버로딩들을 살펴보면, RandomIt라는 타입으로 정의되어 있다. RandomIt는 보통 Random Access Iterator(임의 접근 반복자)를 가리킨다.
  • Random Access Iterator의 예시로는
    • 포인터
    • std::vector<T>::iterator
    • std::array<T, N>::iterator
    • std::deque<T>::iterator
  • 등이 있다.

예시

위에서 말한 Random Access Iterator들을 이용해서 sort 함수에 범위를 지정해보자.

• 배열: 포인터

  int arr[] = {5, 4, 3, 2, 1};
  std::sort(arr, arr + 5);
  // result: [1, 2, 3, 4, 5]
  

  • 배열을 선언하면 배열 이름은 첫 번째 요소에 대한 포인터로 암시적으로 변환된다.
  • 따라서 first에는 배열 이름을 넣어줄 수 있다.
  • last는 배열의 포인터 + 정렬할 길이처럼 사용할 수 있고, 보통 포인터 + 전체 배열 길이 로 사용한다.
• vector: std::vector<T>::iterator

  std::vector<int> v = {5, 4, 3, 2, 1};
  std::sort(v.begin(), v.end());
  // result: [1, 2, 3, 4, 5]
  

  • vector의 첫 요소를 가리키기 위해서 v.begin()을 사용한다.
  • 범위의 끝은 v.end()로 받아올 수 있다.
• array: std::array<T, N>::iterator

  std::array<int, 5> arr = {5, 3, 4, 1, 2};
  std::sort(arr.begin(), arr.end());
  // result: [1, 2, 3, 4, 5]
  

• deque: std::deque<T>::iterator

  std::deque<int> deq = {5, 4, 3, 2, 1};
  std::sort(deq.begin(), deq.end());
  // result: [1, 2, 3, 4, 5]
  

• 정렬에 사용되는 함수이다.
• 반환값은 bool 타입이고, 첫 번째 인자가 두 번째 인자보다 앞에 와야 하는 경우 true를, 뒤로 가야 하는 경우 false를 반환한다.
• $Compare$Compare라는 명명된 요구 사항을 지켜야 한다. 이 요구 사항을 지키지 않으면 당신의 프로그램은 터져버린다,,,

비교 함수 작성하기

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

위 형식으로 정의하면 된다.

bool comp(Type1 a, Type2 b);

이렇게도 정의할 수 있지만, a 또는 b의 값을 함수 안에서 수정해서는 안 된다.

비교 함수 예시

• 비오름차순(≒ 내림차순)으로 정렬하는 예시

  bool comp(int a, int b)
  {
  	return a > b;
  }
  

  • 큰 숫자가 앞으로 와야 하므로, a가 b보다 클 때 true를 반환하면 된다.
• 문자열의 길이순(만약 같다면 사전순)으로 정렬하는 예시

  bool comp(string a, string b)
  {
  	int aLen = a.length(), bLen = b.length();
  	if (aLen == bLen)
  		return a < b;
  	return aLen < bLen;
  }
  

  • 길이가 작은 쪽이 앞으로 와야 하므로, aLen이 더 작을 때 true를 반환해야 한다.
  • BOJ 1181 단어 정렬에서 사용해보자.
• pair<int, int>에서 second를 기준으로, 만약 second가 같다면 first를 기준으로 비내림차순(≒ 오름차순) 정렬하는 예시

  bool comp(pair<int, int> a, pair<int, int> b)
  {
  	if (a.second == b.second)
  		return a.first < b.first;
  	return a.second < b.second;
  }
  

  • BOJ 1931 회의실 배정에서 사용해보자.

명명된 요구 사항: $Compare$Compare

• 기본적으로 함수가 두 인자를 비교할 때, 일관된 순서를 유지하도록 하는 것이다.
• cppreference에서 자세한 내용을 확인할 수 있다.
• 자세한 내용은 다른 글로 쓰겠다...

https://en.cppreference.com/w/cpp/algorithm/sort