[C++] 정렬 함수 사용법 (sort 함수, 정렬 기준 다양하게)

이전 글을 비롯한 여러 예제 풀이에서 정렬을 사용했던 적이 있다.

단순한 일차원 vector나 array 외에도 다양한 차원의 자료형을 다뤄야 하는 상황이 있으며, 그 때 당황하지 않고 정렬을 사용할 수 있도록 공부하고자 C++에서의 sort 함수에 대해 정리해보도록 한다.

---

sort 함수는 "시작과 끝"을 알려주면 동작하며, 시작과 끝을 정의하는 방식이 벡터와 배열에서 조금씩 다르다.

sort함수 기본형

C++에서 sort함수를 사용하는 기본적인 방법은 아래와 같다.

sort(시작주소, 끝주소);

여기서 시작주소와 끝주소는 범위를 나타낸다.

 

벡터에서는 .begin(), .end()로 범위를 줄 수 있고, 배열에서는 포인터 방식으로 범위를 준다.

벡터를 sort하는 방법

벡터는 .begin()과 .end()로 간단하게 정렬할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 3, 2, 4, 1};
    sort(v.begin(), v.end()); // 오름차순 정렬
    for (int x : v)
        cout << x << ' ';
}

출력 결과는 1 2 3 4 5로 v.begin()부터 v.end()까지 오름차순으로 정렬한 것이다.

배열을 sort하는 방법

배열은 포인터처럼 다룬다.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[5] = {5, 3, 2, 4, 1};
    sort(arr, arr + 5); // 오름차순 정렬
    for (int i = 0; i < 5; i++)
        cout << arr[i] << ' ';
}

sort 함수 안에 있는 arr은 배열의 시작 주소, arr + 5는 배열의 끝 주소를 나타낸다.

즉, 배열도 시작과 끝을 포인터로 넘기기만 하면 쉽게 정렬할 수 있다.

직접 비교 기준을 설정하여 정렬하는 방법

예를 들어 큰 값부터 작은 값으로 정렬하고자 한다면, 비교 함수를 만들어주면 된다.

bool cmp(int a, int b) {
    return a > b; // 큰 값이 앞에 오게
}

벡터든 배열이든 비교 함수를 sort에 넘겨주면 된다.

sort(v.begin(), v.end(), cmp); // 벡터
sort(arr, arr + 5, cmp);       // 배열

람다 함수를 이용한 더 간결한 sort 사용

람다(lambda) 함수는 일회성 비교 함수를 만드는 방법이며 그 형태는 아래와 같다.

[](매개변수들) -> 반환형 { return 비교식; }

정의할 필요 없이 sort 안에서 바로 만든다.

sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;
});

배열에 대해서도 마찬가지로 할 수 있다.

sort(arr, arr + 5, [](int a, int b) {
    return a > b;
});

두 개 이상의 값을 가지는 경우 (pair 정렬)

직전 글의 회의실 문제 (시작 시간, 끝나는 시간)처럼 두 값이 있을 때에도 이를 정렬할 수 있다.

vector<pair<int, int>> meetings = {{1, 4}, {3, 5}, {0, 6}};

/* 분류 기준 함수를 따로 정의하는 방법 */
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.second == b.second)
        return a.first < b.first; // 끝나는 시간이 같으면 시작 시간 기준
    return a.second < b.second;   // 끝나는 시간 기준 정렬
}

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

vector<pair<int, int>> meetings = {{1, 4}, {3, 5}, {0, 6}};

/* 람다 함수를 이용한 정렬 */
sort(meetings.begin(), meetings.end(), [](pair<int, int> a, pair<int, int> b) {
    if (a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
});

두 방법 모두 같은 결과를 출력한다.

---

정렬은 코딩테스트에서 가장 많이 등장하는 기본 스킬이다.
특히 그리디 알고리즘 문제에서는 정렬을 잘 다루는 것이 정답과 직결된다.

 

요약하자면,

• sort(arr.begin(), arr.end()); : 기본 오름차순 정렬
• sort(arr.begin(), arr.end(), cmp); : 내가 만든 비교 함수로 정렬
• sort(arr.begin(), arr.end(), [](auto a, auto b){ 비교식 }); : 람다 함수로 더 깔끔하게 정렬
• 구조체나 복잡한 데이터에 대해서는 비교 기준을 명확히 해야하며, 람다 함수를 사용하면 깔끔한 코드를 작성할 수 있다.