[C++ STL] Sort() 사용법 및 compare 함수

sort 함수는 C++ STL에서 제공하는 함수로써 정렬에 이용되며 <algorithm> 헤더를 include 하여 사용 할 수 있다.

 

각종 알고리즘 문제에서도 간단하게 사용 할 수 있어서 자주 쓰이는데, 이 함수의 시간 복잡도는 nlogn이다.

 

시간 복잡도에 대해 조금 더 설명해보면, sort 함수의 구현은 intro sort라는 정렬 방법을 바탕으로 했는데, 이 방법은 quick sort에 heap sort와 insertion sort를 섞은 방식으로  평균 nlogn, 최악의 경우 n^2의 시간 복잡도를 가지는 quick sort와는 달리, 최악의 경우에도 nlogn을 보장한다.

 

함수의 인자와 사용법을 살펴보면

 

vector <int> v(10,10);
sort(v.begin(),v.end()); // 1
sort(v.begin(),v.end(),custom_func); // 2

 

1번의 경우)

첫 번째 인자: iterator(or 포인터)에서 정렬을 시작 할 부분

두 번째 인자: iterator(or 포인터)에서 정렬을 마칠 부분

 

이 때 중요한 점은 [begin,end) 범위로 정렬을 한다는 것이다. (begin <= 범위 <end)

즉, 예를 들어 int a[100]에서 0~10번 인덱스까지 정렬한다고 했을 때, 첫 번째 인자에는 배열의 시작 주소인 a을 넣고, 두 번째 인자에는 a+9가 아닌 a+10을 넣어야 한다는 것이다.

 

이렇게 두 개의 인자만 넣어주는 경우 오름차순으로 정렬이 된다.

 

2번의 경우)

첫 번째 인자, 두 번째 인자 : 1번과 동일

세 번째 인자 : 정렬을 어떤 식으로 할 것인지 알려주는 함수

 

이 세 번째 인자를 compare함수라고 많이들 부르던데, 이 부분에는 bool형 함수나 혹은 수식(수식도 0또는 1이 나오므로)을 넣어 줄 수 있다.

함수를 사용하는 경우, 두 개의 매개 변수를 받도록 선언하면 sort함수에서 자동으로 값을 할당한다.

 

예시와 함께 살펴보면, 

 

vector <int> v(10,10);
 
bool compare(int i, int j) { return i > j; }
 
sort(v.begin(),v.end(),compare); // 2

 

이 때, 함수의 이름은 당연히 compare가 아닌 어떤 것이라도 상관없으며, 주의해야 할 점은 인자로는 compare()가 아닌 compare를 넣어줘야 한다는 것이다.

 

sort 함수에서 세 번째 인자로 들어간 함수를 인식하여, 자동으로 앞에 수를 i, 뒤에 수를 j에 넣어주게 되는데, i > j가 참이면 1, 거짓이면 0을 반환하는 함수이므로, i가 j보다 클 경우 sort를 실시하게 되어 내림차순으로 정렬된다.

 

여기까지 읽었을때 잘 이해가 안 될 수도 있기 때문에,

백준 문제 https://www.acmicpc.net/problem/11650 풀이를 통해 설명하면

11650번: 좌표 정렬하기

BOJ_11650 좌표 정렬하기

 

위 문제는 x와 y라는 두 개의 값을 가지는 좌표들을 x따로 y따로 정렬해야 하는 문제이다.

 

using namespace std;
#include <iostream>
#include <vector>
#include <algorithm>
 
bool sorting(pair <int,int> p, pair <int,int> p2) { // compare 함수
    if (p.first == p2.first) { // x 좌표가 같다면
        return p.second < p2.second; // y 좌표를 오름차순으로
    }
    
    return p.first < p2.first; // x 좌표가 같지 않다면 x 좌표를 오름차순으로
}
 
int main(void) {
 
    vector < pair <int, int> > v;
    
    while (n--) {
        cin >> t1 >> t2;
        v.push_back(make_pair(t1, t2));
    }
 
    sort(v.begin(), v.end(), sorting);
 
    for (auto x : v) {
        cout << x.first << " " << x.second << "\n";
   }
}

 

위와 같은 함수를 만듦으로써 쉽게 풀 수 있다.

 

위 코드처럼 pair<int, int>를 담은 벡터를 정렬한다고 하면, compare 함수의 인자들도 pair <int, int> 형으로 받아준 뒤

위에서 구현 한 것처럼 사용 할 수 있다.

 

동일한 방법으로 https://www.acmicpc.net/problem/10825

10825번: 국영수

문제도 compare 함수를 정의하여 쉽게 풀 수 있다.

 

참고 링크 : [백준 / BOJ_10825] 국영수