[C++] algorithm sort()

MTTW·2021년 1월 29일

C++

목록 보기

2/4

이 게시물은 @kjh107704의 궁금증으로부터 시작된다.

알고리즘 문제를 풀다보면 아주 유용하게 쓰는 <algorithm> 라이브러리 내 sort() 함수의 작동방식에 대한 궁금증이다. 나도 항상 쓰면서 헷갈렸고 아직도 헷갈리고 있으니 총 정리해서 이 글에 담는다.

1.1. 기본적인 사용법

기본적인 sort() 함수 사용 방법은 아래와 같이 소개할 수 있다.

sort(배열의 시작, 배열의 끝 + 1, compare 조건 함수)

// 배열의 경우
int array[5] = {4, 2, 5, 10, 1};
sort(array, array + 5);

// 벡터의 경우
vector<int> vec;
sort(vec.begin(), vec.end());

sort() 함수는 기본적으로 오름차순 정렬을 해준다. 다른 조건에 따라 정렬하고 싶다면 compare 함수를 만들거나 이미 존재하는 함수를 사용할 수 있다.

1.2. `functional` 함수 객체 사용하기

functional 라이브러리는 priority queue에서 처음 만났는데 sort에도 사용할 수 있다는 건 이번에 처음 알았다.

#include <functional>
// 배열의 경우
sort(array, array+5, less<>());		// 오름차순 정렬
sort(array, array+5, greater<>());	// 내림차순 정렬

// 벡터도 같다
sort(vec.begin(), vec.end(), less<>()); 	// 오름차순 정렬
sort(vec.begin(), vec.end(), greater<>());	// 내림차순 정렬

1.3. 직접 compare 함수 만들기

compare 함수는 배열 내부의 요소를 받고 bool 타입을 리턴한다. 이때 도대체 어떤 조건에서 true를 돌려주면 되는건지는 항상 헷갈린다. @kjh107704와 어제 계속 헷갈려했던 부분이기도 하다.

C++ 라이브러리를 정리해둔 사이트를 참고하니 아래와 같이 설명하고 있다.

요약하자면 true를 리턴하면 앞에 위치한 값이 앞에 남는다. 따라서 아래와 같이 만들 수 있다.

// 오름차순 정렬
bool comp_less(int num1, int num2){
    // num1이 작으면 먼저 와야한다
    if(num1 < num2) return true;
    else return false;
}
// 오름차순 간단한 버전
bool comp_less_easy(int num1, int num2){
    return num1 < num2;
}

// 내림차순 정렬
bool comp_greater(int num1, int num2){
    if(num1 > num2) return true;
    else return false;
}
// 내림차순 간단한 버전
bool comp_greater_easy(int num1, int num2){
    return num1 > num2;
}

// 적용
sort(vec.begin(), vec.end(), comp_less);
sort(vec.begin(), vec.end(), comp_less_easy);
sort(vec.begin(), vec.end(), comp_greater);
sort(vec.begin(), vec.end(), comp_greater_easy);

1.3.1. 사실상 우리가 자주 쓰는 방법

하지만 때로는 이것보단 복잡한 방식의 compare 함수가 필요하다.

구조체를 정렬하거나
pair<int, int>를 정렬하거나 (기본적으로 first를 기준으로 정렬해준다.)
string을 길이순으로 정렬하거나

등등의 경우에 커스텀 함수도 위와 같은 방식으로 만들 수 있다.

예를 들어보자. vector<pair<string, int>>를 정렬할 때

string의 길이 순으로 정렬하되
길이가 같다면 int를 기준으로 내림차순으로 정렬한다.

bool custom_comp(pair<string, int> p1, pair<string, int> p2){
    if(p1.first.length() == p2.first.length()){
        // string 길이가 같다면 p1.second가 클 때 앞에 정렬된다.
        return p1.second > p2.second;   
    }
    // p1 string의 길이가 짧으면 앞에 정렬된다.
    return p1.first.length() < p2.first.length();   
}

int main(){
    vector<pair<string, int>> customvec;
    customvec.push_back(make_pair("kjh", 1));
    customvec.push_back(make_pair("kes", 2));
    customvec.push_back(make_pair("jh", 45));
    customvec.push_back(make_pair("es", 12));
    customvec.push_back(make_pair("mttw", 20));
    sort(customvec.begin(), customvec.end(), custom_comp);

    int c_size = customvec.size();
    for(int i=0; i<c_size; i++){
        printf("(%s, %d)\n", customvec[i].first.c_str(), customvec[i].second);
    }
    
    return 0;
}

실제 결과 👇 조건대로 string길이 오름차순대로, 같은 경우에는 숫자 내림차순으로 정렬된 것을 확인할 수 있다.

1.4. 연산자 오버로딩

사실 연산자 오버로딩은 평소에 굳이 쓸 생각을 못했다. 1.3절에서 언급한 방법으로 해결이 되기 때문이다. 하지만 호기심은 전염된다. @kjh107704이 물어보다가 operator 오버로딩도 잠깐 언급했는데 오버로딩으로 쓴다면 <를 써야하는건지 >를 써야하는건지 모르겠다는 질문이었다.

나도 갑자기 궁금해져서 직접해봤다.
사실 정답은 위에서 언급했던 사이트에 나와있었다.

여기까지 온거 한 번 해보자!
(class로 했지만 구조체도 같은 방식으로 된다.)

class Number{
    private :
        int x, y;
    public :
        Number(int _x, int _y){
            x = _x;
            y = _y;
        }
        // < 연산자 오버로딩
        // 앞으로 Number < Number 연산은 y값을 비교하는 방식으로 진행된다.
        bool operator < (Number &n1){
            return y < n1.y;
        }
        void print(Number &n){
            printf("(%d, %d)\n", n.x, n.y);
        }
};

int main(){
    Number num1(1, 0);
    Number num2(3, 1);
    Number num3(2, -1);
    
    vector<Number> vec;
    vec.push_back(num1);
    vec.push_back(num2);
    vec.push_back(num3);
    
    // 연산자 오버로딩을 사용했기 때문에 compare함수를 쓰지 않는다.
    sort(vec.begin(), vec.end());

    for(int i=0; i<3; i++){
        vec[i].print(vec[i]);
    }
    return 0;
}