<algorithm>을 활용한 정렬

CP를 하면서 헷갈리는 것을 정리했다.

 

배열 정렬과 벡터 정렬

 

// 벡터(n은 정렬할 원소의 개수)
sort(vec.begin(), vec.end()); // 오름차순
sort(vec.begin(), vec.begin() + n); // 오름차순
sort(vec.begin(), vec.end(), greater<>()); // 내림차순
 
// 배열
sort(arr, arr + n); // 오름차순
sort(&arr[0], &arr[n]); //
sort(arr, arr + n, greater<>()); // 내림차순

 

char 및 string의 정렬도 똑같이 작동한다.

비교 함수인 greater<>()에 자료형을 정해주지 않고 비워놓은 것을 확인할 수 있다. 이렇게 자료형을 쓰지 않아도 되는 것을 'transparent functors'이라고 하며, C++ 14에 도입되었다.

 

string arr[6] = {"abc", "bca", "cab", "cba", "bac", "acb"};
for(auto &el : arr) cout << el << " "; // abc bca cab cba bac acb
sort(arr, arr + 6);
for(auto &el : arr) cout << el << " "; // abc acb bac bca cab cba 
 
string arr[6] = {"abc", "bca", "cab", "cba", "bac", "acb"};
for(auto &el : arr) cout << el << " "; // abc bca cab cba bac acb
sort(arr, arr + 6, greater<>());
for(auto &el : arr) cout << el << " "; // cba cab bca bac acb abc

 

pair 컨테이너에서의 정렬

 

sort(v.begin(), v.end());
sort(v.begin(), v.end(), greater<>());

 

아래는 직접 비교 함수를 구현한 예시이다. first는 오름차순, second는 내림차순으로 정렬했다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
struct cmp
{
    bool operator()(const std::pair<int,string> &left, const std::pair<int,string> &right) {
      if (left.first == right.first) {
        return left.second > right.second;
      }
      return left.first < right.first;
    }
};
 
int main(){
  vector<pair<int, string> > v;
  v.emplace_back(pair<int, string>(20, "aa"));
  v.emplace_back(pair<int, string>(21, "bb"));
  v.emplace_back(pair<int, string>(22, "cc"));
  v.emplace_back(pair<int, string>(20, "ab"));
  v.emplace_back(pair<int, string>(21, "bc"));
 
  sort(v.begin(), v.end(), cmp());
  for (int i = 0; i < v.size(); i++)
    cout << v[i].first  << " " <<  v[i].second << endl;
//  20 ab
//  20 aa
//  21 bc
//  21 bb
//  22 cc
}

 

사용자 정의 자료형

 

struct node
{
    string name;
    int age;
};
 
// 이름 기준 오름차순 정렬
bool cmp1(const node &a, const node &b){
  return a.name < b.name;
}
 
// 이름 기준 내림차순 정렬
bool cmp2(const node &a, const node &b){
  return a.name > b.name;
}
 
// 이름을 기준으로 오름차순 정렬 하되, 이름이 같으면 나이를 기준으로 내림차순
bool cmp3(const node &a, const node &b){
  if (a.name == b.name) return a.age > b.age;
  return a.name < b.name;
}
 
sort(v.begin(), v.end(), cmp1);

 

비교 연산자 오버로딩을 해서 정렬하려면 다음과 같이 하면 된다. 다만 이 경우에는 '>' 연산자는 오버로딩 할 수 없고, '<' 연산자만 오버로딩 할 수 있다. 내림차순으로 정렬하고 싶다면 'return a.name > b.name'과 같이 하면 된다.

 

struct node
{
    string name;
    int age;
};
bool operator < (const node &a, const node &b) {
    return a.name < b.name;
}
 
// friend를 써서 struct의 안쪽으로 넣을 수도 있다.
struct node
{
    string name;
    int age;
    friend bool operator < (const node &a, const node &b) {
        return a.name < b.name;
    }
};
 
sort(v.begin(), v.end());