컨테이너 정렬 함수 sort()

🔎 sort()

sort()는 Array, vector등 컨테이너들의 요소를 정렬하는 함수이다.
$O(nlog(n))$의 시간복잡도를 가진다.

sort(first, last, 비교함수)

first → 컨테이너의 시작 이터레이터

last → 컨테이너의 마지막 이터레이터(마지막 주소값의 + 1)

비교함수 → 정렬방식(오름차순, 내림차순, 커스텀)에 대한 함수

비교함수를 부분을 비우면 기본적으로 오름차순(1, 2, 3, …) 정렬하며
greater<자료형>()을 넣어 내림차순, less<자료형>()을 넣어 오름차순으로 변경 가능하다.
또한 비교함수를 직접 제작하여 여러 경우에 사용 가능하다.

사용 예시

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a[5] = { 2, 4, 3, 5, 1 };
    sort(a, a + 5);                 //자동 오름차순 정렬
    for (int i = 0; i < 5; i++) {
        cout << a[i] << " ";
    }
    cout << "\n";

    sort(a, a + 5, greater<int>()); //내림차순 정렬
    for (int i = 0; i < 5; i++) {
        cout << a[i] << " ";
    }
    cout << "\n";
}

출력 결과

1 2 3 4 5
5 4 3 2 1

🔎 비교 함수

sort()는 pair, tuple등 2개 이상의 값을 가지고 있는 경우에도 정렬이 가능하다.
원하는 정렬기준을 함수화(bool 함수)해서 sort()의 매개변수로 넣어주면 된다.

비교함수는 두 요소 간 크기를 비교하여 그 결과를 리턴하는 함수여야 하므로 bool로 선언해야하며
첫번째 매개변수를 a, 두번째 매개변수를 b라고 할 때
a < b 로 리턴하면 오름차순, a > b 로 리턴하면 내림차순 정렬한다.

만약 2개의 값을 가지고 있는 pair에서 first로 오름차순 정렬하되
first의 값이 같은 경우에는 second로 내림차순 정렬하고자 한다면
아래와 같이 함수를 구성하면 된다.

사용 예시

#include <bits/stdc++.h>
using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b) {  //비교함수
    if (a.first == b.first) {
        return a.second > b.second;
    }
    return a.first < b.first;
}

int main() {
    vector<pair<int, int>> a;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 3; j++) {
            a.push_back({ i, j });
        }
    }

    sort(a.begin(), a.end(), cmp);

    for (int i = 0; i < 15; i++) {
        cout << "{ " << a[i].first << ", " << a[i].second << " }\n";
    }
    return 0;
}

출력 결과

{ 0, 2 }
{ 0, 1 }
{ 0, 0 }
{ 1, 2 }
{ 1, 1 }
{ 1, 0 }
{ 2, 2 }
{ 2, 1 }
{ 2, 0 }
{ 3, 2 }
{ 3, 1 }
{ 3, 0 }
{ 4, 2 }
{ 4, 1 }
{ 4, 0 }