sort 함수 사용법

Algorithm 헤더에 있는 sort 함수에 관하여 정리해보도록 하자.

sort(배열의 시작점 주소, 배열의 마지막점 주소)

- 개념 : sort(start, end) , start와 end 범위에 있는 요소들을 오름차순 정렬해주는 함수

           퀵 정렬을 기준으로 함수가 구현되어 있어서, 시간 복잡도는 O(nlogn)이다.

- 사용법

  크기가 n인 배열 arr, 백터 vec이 있다고 할때

• sort(arr, arr +n);
• sort(vec.begin(), vec.end());
• sort(vec.begin(), vec.end(), cmp);  → 비교함수 cmp를 만드는 경우
• sort(vec.begin(), vec.end(), greater<자료형>()); → 내림차순 정렬을 사용하는 경우

greater : 첫번째 인자가 두번째 인자보다 크면 true 반환 (bool) → #include <functional> 추가해야 greater STL 사용가능

비교함수 만드는 경우를 자세히 살펴보자.

vector에 인자가 1개면 만들 필요없지만, 인자가 구조체인 경우 혹은 내림 차순을 greater<>() 사용 안할때

비교함수를 만들어 줘야한다.

주의할 점은 const와 & 연산자를 사용해야 한다는 점이다.

(비교하는 과정에서 값의 수정이나 변경이 없으므로)

코드를 통해 보자.

1. 내림차순 정렬

//내림차순 정렬
bool cmp(const int &a, const int &b) {
    return a > b; 
}
 
//다른 식으로 쓴다면?
bool cmp(const int &a, const int &b) {
    if(a > b) return true;
    else return false;
}

2. 인자가 구조체인 경우

struct Point {
    int x, y;
};
 
//x를 오름차순으로 정렬하고,x가 같다면 y도 오름차순으로 정렬
bool cmp(const Point &a, const Point &b) {
    if (a.x < b.x) {
        return true;
    }
    else if (a.x == b.x) {
        return a.y < b.y;
    }
    else {
        return false;
    }
}
 
//다른식으로 표현하자면
bool cmp(const Point &a, const Point &b) {
    if (a.x == b.x) {
       return a.y < b.y;
    }
    else{
        return a.x < b.x;
    }
}