정렬

STL sort

정렬

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

vector<int> v = {1, 4, 6, 2, 3};
sort(v.begin(), v.end());
stable_sort(v.begin(), v.end());

커스텀 정렬

bool cmp(int a, int b){
	return a < b;
}
sort(a, a+5, cmp);
stable_sort(a, a+5, cmp);

sort(v.begin(), v.end(), cmp);
stable_sort(v.begin(), v.end(), cmp);

주의사항1: 비교 함수는 두 값이 같을 때 false를 반환

struct A{
	int a;
	int b;
}

//{1, 2}와 {1, 3}를 비교
bool cmp(A m, A n){
	if(m.a == n.a) m.b < n.b;
	return m.a < n.a
}

리턴 값을 보면 <= 가 아닌 <을 사용한 것을 볼 수 있다.

같다 가 true가 되버리면 내부적으로 로직이 꼬일 수 있다.

주의사항2: 비교함수의 인자로 STL 또는 클래스 객체를 전달시 레퍼런스 사용

객체끼리의 비교는 함수 내에 객체를 전달할 때 복사 비용이 많이 든다.

따라서 레퍼런스로 넘겨서 주소값 8바이트만 복사되도록 하는 것이 좋다.

근데 longlong, int, short, char, bool, double, long double 같은 숫자형 타입은 어차피 8바이트 이하라서 상관없다.

위의 예시코드도 객체이므로 레퍼런스로 보내는게 맞다.

근데 굳이 따져보면 A 구조체의 용량도 8바이트(4바이트+4바이트)이므로 사실 똑같다.