std :: sort (begin, end)가 범위를 수정했는지 확인

Question

std::sort(begin, end)에 대한 호출이 실제로 범위를 수정했는지 여부를 확인하는 가장 우아한 방법은 무엇입니까? 여기

내 두 개의 아이디어가 있습니다 :

(A)를 확인하면 이미 정렬 O (N) :

if (already_sorted(begin, end)) { return false; } 
std::sort(begin, end); 
return true; 

(b)의 비교에서 변경 내용 추적 (이 안전합니까?)

bool modified = false; 
std::sort(begin, end, [&modified](T a, T b){ modified |= a<b; return a<b; }); 
return modified; 

더 좋은 방법이 있습니까?

Answer 1

"시작"에서 "끝"까지 구조를 반복하지 않는 한 이미 정렬되어 있는지 알 수 없으므로 수행 할 수있는 최선은 O (n)입니다.

나는 첫 번째 선택 인 already_sorted에 갈 것이다.

Answer 2

배열이 시작된 순서와 다른 순서로 돌아 왔는지 확인하는 것보다 O (n) 검사를 더 잘 수행 할 수 있다고 생각하지 않습니다. 주문이 작동하지 않는다면 상황을 확인하기 위해 비교자를 하이재킹합니다. 이론적으로 정렬 함수는 아무 것도 움직이지 않고 원하는 비교를 할 수 있기 때문에 가능합니다. 또한 스왑이 수행되었는지 여부를 추적하는 것은 주문이 변경된 경우 반드시 알려주지는 않습니다. 정렬이 일을 끝내고 같은 순서로 복원 할 수 있기 때문입니다 (예를 들어 힙을 생각하십시오).

Answer 3

동일한 값을 두 개 교환하면 범위가 변경된 것으로 간주합니까? 이 경우 already_sorted 변형은 작동하지 않습니다.

그렇지 않으면 가장 빠른 방법이어야합니다.

Answer 4

정렬 할 개체가 클래스 형식 인 경우 std::swap이 호출하는 operator = 오버로드가있는 하위 개체를 도입 할 수 있습니다. 그러나 이론적으로 객체가 스왑 된 다음 다시 스왑 된 경우 오탐 (false positive)을 허용 할 수 있습니다.

아마도 총 실행 시간이 상당히 걸릴 때까지 already_sorted을 사용해야합니다.