[코딩테스트 / C++] C++ STL Sort

STL sort

int a[5] = {5,4,3,2,1}
sort(a, a+5);

vector<int> b = {5,4,3,2,1};
sort(b.begin(), b.end()); // sort(b.begin(), b.begin()+5);

코딩테스트에서는 STL에 있는 sort 함수를 써서 정렬을 딱 한 줄의 코드로 수행이 가능하다.

STL sort는 퀵 소트를 기반으로 하지만 리스트가 불균등하게 쪼개지는 상황이 계속 반복되어서 재귀에서의 깊이가 너무 깊어지면 O(NlgN)이 보장되는 정렬 알고리즘으로 나머지를 처리한다. 그래서 STL sort는 최악의 경우에도 O(NlgN)이 보장된다. 다만 sort 함수는 stable sort가 아니어서 동일한 우선순위를 가진 원소들 사이의 상대적인 순서가 보존되지 않을 수 있다. 꼭 stable sort가 필요하다면 stable_sort 함수를 사용하면 된다. stable_sort 또한 sort 함수와 사용법이 똑같다.

또한 pair, tuple에는 이미 대소 관계가 우리에게 익숙한대로 먼저 제일 앞의 원소의 대소를 비교하고, 값이 같으면 그 다음 원소의 대소를 비교하는 방식으로 정해져있다. 예를 들어 pair에서 {2, 5} < {3, -2}고 tuple에서 {2, 1, 0} > {2, -2, 6}이다. 그래서 좌표를 정렬하거나 기타 여러 속성이 있는 원소를 정렬할 때 별도로 구조체를 둘 필요가 없고 pair나 tuple 등을 이용하면 된다.

bool cmp(int a, int b){
    if(a%5 != b%5) return a%5<b%5;
    return a<b;
}

int a[7] = {1,2,3,4,5,6,7}
sort(a, a+5);

STL sort에는 비교 함수를 내가 정해서 넘겨줄 수 있다. 예를 들어 int형을 크기 순으로 정렬하고 싶으면 위의 코드와 같이 하면 되는데 int형을 5로 나눈 나머지 순으로, 5로 나눈 나머지가 같다면 크기 순으로 정렬하고 싶다고 할때 위 코드와 같이 작성하면 된다. 이렇게 하면 배열 a가 5, 1, 6, 2, 7, 3, 4로 정렬된다. 이처럼 비교 함수 cmp(int a, int b)는 a가 b의 앞에 와야할 때 true를, 그렇지 않을 때에는 false를 반환해야 한다.

stl sort 사용시 주의사항

// 올바른 예
bool cmp(int a, int b){
    return a>b;
}

// 틀린 예
bool cmp(int a, int b){
    if(a>=b) return true;
    return false;
}

a가 b의 앞에 와야할 때만 true를 반환해야 하니 두 값이 같을 때 혹은 우선순위가 같을 때에는 반드시 false를 반환해야 한다.

// 올바른 예
bool cmp(const string &a, const string &b){
    return a.back() < b.back();
}

// 틀린 예
bool cmp(string a, string b){
    return a.back() < b.back();
}

인자를 전달할 때 reference로 전달하면 값 복사 시간을 줄일 수 있다. 또한 값 변경을 막기위해 const를 붙인다.