[알고리즘] Sort 함수 이해

C++ 에서 Algorithm에 들은 sort 사용시,

 

quickSort이면서 좀 더 복합된(?) 로직으로 구현되어있다.

 

해당 함수는 

 

sort(시작, 끝, 비교함수) 로 구현할 수 있는데,

 

비교함수 구현시, bool type을 return 해주어야 하며,

 

True 이면 sort함수는 왼쪽이 오른쪽보다 먼저 나오게 해준다.
 * 사실 이게 좀 헷갈림..

 

비교함수 구현시 const &주소값으로 인자를 설정하여 reference로 받아 구현하는 경우가 많다.

 

이는 null 방지 혹은 값을 변경할수 없도록 const 를 붙여 구현하는걸로 보인다.

 

아래는 간단한 백준 문제와 이에 sort 및 비교함수를 사용하여 간단히 해결했다.

 

https://www.acmicpc.net/problem/11651

11651번: 좌표 정렬하기 2

 

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;


bool comp(const pair<int, int> &a, const pair<int, int> &b){
	if (a.second > b.second){
		return false;
	}
	else if (a.second == b.second){
		return a.first < b.first;
	}
	else {
		return true;
	}
}

int main(){

	int n,inp1,inp2;
	vector<pair<int, int> > v;
	scanf("%d", &n);

	for (int i = 0; i < n; i++){
		scanf("%d %d", &inp1, &inp2);
		v.push_back(make_pair(inp1, inp2));
	}

	sort(v.begin(), v.end(), comp);


	for (int i = 0; i < n; i++){
		printf("%d %d\n", v[i].first, v[i].second);
	}

	return 0;
}