비교 함수 / STL sort

비교함수

bool compare(T a, T b);

• a가 b보다 무조건 앞에 나와야 한다면 true, 그렇지 않으면 false를 반환
• 비교함수는 Strick Weak Ordering을 만족해야 한다

 

Strick Weak Ordering

• 이항 관계 R(a, b)에 대해서 a가 b보다 반드시 앞에 나와야 한다면 참, 그렇지 않으면 거짓이라고 하자
• 비교성: a가 b보다 앞에 나와야 한다면 R(a,b)는 참, R(b,a)는 거짓이다. 이 경우 a와 b를 비교할 수 있다고 한다.
• 비비교성: a가 b와 동등하다면 R(a,b), R(b,a)는 둘 다 거짓이다. 이 경우 a와 b를 비교할 수 없다고 한다.
• 아래 조건을 모두 만족해야 한다.
  • 비반사성: 모든 a에 대하여 R(a,a)는 거짓
  • 비대칭성: 모든 a, b에 대하여 R(a,b)가 참이면 R(b,a)는 거짓
  • 전이성: 모든 a, b, c에 대하여 R(a, b), R(b, c)가 참이면 R(a, c)는 참
  • 비비교성의 전이성: 모든 a, b, c에 대하여 R(a, b), R(b, a), R(b, c), R(c, b)가 거짓이면, R(a, c), R(c, a)는 거짓 (즉,a=b=c)

---

STL sort

• [first, last)를 감소하지 않는 순서 정렬
• comp: 비교함수
• 시간복잡도: O(NlogN)
• STL
  • #include<algorithm>
  • std::sort(first, last);
  • std::sort(first, last, comp);

 

• 오름차순

#include<bits/stdc++.h>
using namespace std;
int main() {
	vector<int> v = { 4,5,2,3,1 };
	sort(v.begin(), v.end());
	for (int i : v)
		cout << i << " "; //1 2 3 4 5
}

 

• 내림차순
  • compare 대신 greater<>()를 사용해도 똑같이 출력된다.

#include<bits/stdc++.h>
using namespace std;

bool compare(int a,int b) {
	return a > b;
}
int main() {
	vector<int> v = { 4,5,2,3,1 };
	sort(v.begin(), v.end(), compare);
	for (int i : v)
		cout << i << " "; //5 4 3 2 1
}