정렬 - sort 함수 다루기 (기본 정렬부터 커스텀까지)

 

배열의 정렬에는 sort()함수가 기본적으로 사용된다.

이 함수를 사용하면 pair의 경우 첫 번째 원소를 기준으로 먼저, 오름차순으로 정렬된다.

int main(){
	vector<int> v;
	for(int i=5; i>=1; i--) v.push_back(i);
    
	// 기본 정렬
	sort(v.begin(),v.begin() + 2); 
	for(int i : v) cout << i << ' '; // 4 5 3 2 1
    
	sort(v.begin(), v.end()); 
	for(int i : v) cout << i << ' '; // 1 2 3 4 5
    
	// 내림차순 정렬
	sort(v.begin(), v.end(), greater<int>()); 
	for(int i : v) cout << i << ' '; // 5 4 3 2 1
}

 

그러나 문제를 풀다보면 pair에서 두 번째 원소를 기준으로 정렬하고 싶거나, first는 내림차순, second는 오름차순 정렬을 하고 싶다던지 하는 경우가 자주 발생한다. 이 경우에는 기본 오름차수 sort로는 해결 할 수 없기 때문에, 커스텀으로 compare 함수나 오브젝트를 만들어 sort(v.begin(), v.end(), compare)의 형태로 사용해야 한다.

 

c++ 레퍼런스에 따르면 sort(first, last, comp)로 사용할 때 comp 함수는 bool 형태의 반환 값을 가지며, bool값이 참이면 fist와 last의 순서를 바꾸지 않고, 거짓이면 순서를 바꾼다.

bool compare(int first, int last){
	return first < last;
}

그래서 예를 들어 first가 last보다 작으면 그대로 두지만 first가 last보다 커서 false를 반환하는 경우 first와 last의 자리를 바꿔서 오름차순으로 정렬하게 된다.

 

그리고 pair끼리 비교하는 경우에는, 이 경우에서는 cmp 함수가 true이면 원소가 swap이 된다.

vector<pair<int, int>> v;
bool cmp(pair<int, int> a, pair<int, int> b){
	return a.first > b.first;
}

int main(){
	for(int i = 1; i <= 10; i++){
		v.push_back({i, 10 - i});
	}
	sort(v.begin(), v.end(), cmp);
}

그래서 위 예시에서 a의 원소가 b의 원소보다 작으면 두 pair가 swap 되므로 내림차순 정렬이 된다.

 

마지막으로, 비교 상황에서 고려해야 할 원소가 두 개 이상인 경우에는 다음과 같이 cmp 함수를 만들어 사용한다.

bool cmp(pair <int,int> a, pair <int,int> b) {
    if (a.first == a.first) { // x 좌표가 같다면
        return b.second < b.second; // y 좌표를 오름차순으로
    }
    return a.first < b.first; // x 좌표가 같지 않다면 x 좌표를 오름차순으로
}

가장 먼저 고려해야 할 원소를 비교한 값을 return 시키고, 그 원소가 같은 경우를 if문 안에 넣어 두 번째 원소를 비교한 값을 return 시키도록 구현한다.