c++ sort시 주의사항

algrorithm 의 sort를 하거나 map/set/priority_queue 의 sort를 할때 compare 함수 정의에 대한 주의사항이 있다.

 

모든 경우를 비교했을때 모두 true면 안된다.

 

즉, false의 경우가 한번은 나와야 한다.

 

나의 경우 아래와 같은 compare함수를 정의했을때 segmentation fault가 발생했다.

bool comp(int& left, int& right)
{
	return a<=b;
}

이 경우, a와 b가 같을 경우 true이기 때문에 자료구조가 {1,1,1,1,1,1,1} 처럼 모두 같을 경우 true만 나오게 되고 sort 내부에서 인덱스 접근이 자료구조의 범위를 넘게 된다.

 

인터넷에서 찾아본 바로는 sort시 전제조건이 strict weak ordering 를 만족해야 한다고 한다.

어떤 값 a,b,c 들에 대해서

1) comp(a,a)는 false를 return
--> a > a 가 true가 되는 것은 모순

2) comp(a,b) = true이면 comp(b,a)는 false를 return
--> a > b 가 true인데 b > a 가 true가 되는 것은 모순

3) comp(a,b) = true, comp(b,c) = true이면 comp(a,c)는 true를 return
--> a > b , b > c가 true인데 a > c 가 false가 되는 것은 모순

4) comp(a,b) = false, comp(b,a) = false이고 comp(y,c) = false, comp(c,y) = false이면 comp(a,c)와 comp(c,a)도 모두 false를 return
--> a > b 가 false이고 b > a가 false라는 것은 a == b 라는 것을 뜻함
즉 a == b이고 b == c 인데 a != c가 되는 것은 모순

처음 코드의 경우 1번 규칙을 위반한다. 따라서 compare함수 정의 시

bool comp(int& left, int& right)
{
	return a<b;
}

크거나 작을 경우에 대해서만 조건을 걸어야한다.

같은경우를 고려해야한다면 그냥 false린턴 또는 다른조건문을 걸어야 한다.

 

추가적인 정보로는 c++ 의 sort경우, 작은 자료구조에는 문제가 나타나지 않지만 충분히 큰 자료구조에는 문제가 발생한다.

충분히 범위가 클경우 sort는 Quick sort알고리즘을 이용하는 것 같다. sort 내부에서 비교시 pivot이라는 중심값을 구해서 pivot과 인덱스들을 비교하는데 계속 true일 시 인덱스들을 계속 ++ 또는 --를 하면서 비교하다가 범위를 넘어서는 것이다.

 

 

안전한 정렬  stable_sort

*Merge Sort 방식.

*정렬 시, 같은 값일 때 원래 순서 유지.

*위의 sort 문제점 해결.

*일반 sort와 사용법 같음.

 

 

 

<참고>

c++ sort 의 비교함수가 true만 리턴할 때 어떤 일이 일어날까요? (tistory.com)

c++ sort 의 비교함수가 true만 리턴할 때 어떤 일이 일어날까요?