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

 안녕하세요. chogahui05입니다. sort 함수의 비교 함수를 작성하실 때, strict weak ordering을 만족하게 작성하여야 한다는 말을 많이 들으셨을 거에요. 그렇게 작성하지 않으면 어떻게 될까요? 라는 질문은 사실 별로 의미가 없어 보입니다. 비교 함수가 무조건 true를 리턴하게 작성이 되었을 때 어떤 일이 일어날까요? 너무 멍청한 코딩인가요?

 

 

 처음 비교함수를 작성하실 때, 이런 식으로 코딩하시지 않으셨나요? 위와 같이 작성이 되었을 때, 어떤 일이 일어날까요? 사실 배열에 들어간 데이터들을 보았을 때, 이 경우도 무조건 compare 함수가 true를 리턴하게 되어 있어요. 똑같은 상황인 셈입니다.

 

 

---

 se.cpp입니다. 이 프로그램의 내용을 봅시다.

 

 이 경우에 프로그램이 어떻게 실행이 될까요?

 

 

 Segmentation fault라고 출력이 되고 강제 종료가 됩니다. sort는 내부적으로 n이 적당히 큰 경우에는 Quick sort를 씁니다. 정렬 ordering이 잘못된 경우된 경우라면, 재귀적으로 계속 Qsort가 호출이 되서, 스택 메모리 부족으로 터지지 않을까요? 아니면, 메모리의 어딘가에 잘못 접근해서 터지는 것일까요? 여기까지만 보고서는 잘 모르겠습니다.

 

 st.cpp를 다음과 같이 작성해 봅시다.

 

 

 저는, arr+490부터, arr+509까지 정렬을 할 거에요. 부분 sort를 하는 셈입니다. 그리고, arr[i]의 v값은 i를 넣도록 하겠습니다. cmp 함수는, 키 값 2개를 비교할 때 호출이 되는 함수인데요. 만약에, 출력되는 값이 490이상, 510 미만이 아니라면 Out of index 때문에 런타임 오류가 났다고 추측해 볼 수 있습니다.

 

 

 510, 511이 있습니다. Out of index 때문에 RTE가 난다는 가설이 맞았던 셈입니다. 그러면, 이 출력 결과를 통해서 내부적으로 어떤 일이 일어났는지만 추측해 봅시다. Key 500이랑 어떠한 값이랑만 비교하고 있다는 것을 알 수 있는데요. 퀵 정렬은 어떠한 뎁스에서, pivot 값하고 다른 값을 compare 합니다. 500이 많이 나왔다는 이야기는, 500이 pivot이였다는 이야기와 같다는 것을 알 수 있어요.

 

 그런데 이 피벗값이 제일 왼쪽에 있는 값이 아니였는데요. 이건 어떻게 정해졌을까요?

 

 

 490이 제일 왼쪽에 있었으므로, arr+491, arr+(491+509)/2, 그리고 arr+509를 뽑습니다. 이 셋은 각각 491, 500, 509입니다. 각각 left, mid, right라고 합시다. compare(a,b)가 true라는 것은, a가 b보다 앞에 와야 한다는 뜻입니다. 그러면, comp(491, 500)을 호출했을 때 T였고, comp(500, 509)를 호출했을 때 T였으므로, 491 > 500 > 509가 됩니다. 이 중 중간값은 500이기 때문에 pivot은 500이 됩니다.

 

 

 이 과정은 간단하게 compare 함수 안에서 배열의 내용을 출력해 보면 알 수 있어요. 이를 Median of Three라고 하는지는 잘 모르겠어요. st.cpp는 500과 특정한 키 값을 계속 비교하다가 RTE가 났었다는 사실을 추측해 볼 수 있습니다.

 

 

---

 그러면 이 경우에는 어떨까요?

 

 

 이번에는 cmp 함수를 아래와 같이 바꿔보았습니다. a.v가 600일 때는 false를 리턴한다. 그렇지 않으면 무조건 true이다.

 

 

 그러면 600과 500을 비교했을 때, false가 리턴되었기 때문에, 그 다음에 601과 500을 비교하지 않음을 알 수 있어요. 대신에, pivot과 509를 비교하는 것을 알 수 있어요. 그 다음에 피벗과 508을, 다음에는 507을, ... 언제까지 비교할까요? 피벗값과 key 값이 false가 나올 때 까지 compare를 할 거에요. 그런데, b.v가 어떤 값이 되었던지간에, a.v가 500이라면 무조건 true를 리턴하기 때문에, Out of index일 때에도 비교를 할 거에요. 어떻게 파티셔닝을 하는지, 내부 소스를 안 보고도 어느 정도 알 수 있습니다.

 

 여담으로, st.cpp와 st2.cpp 둘 다 segmentation fault가 출력되었습니다. 인덱스 접근 때문입니다. [490, 510)에 속하지 않는 키인 489, 488이 출력되었기 때문입니다.

 

 

---

 그러면 제 환경에서는 왜 RTE가 떴을까요? stl_algo.h에는, sort의 구현이 있습니다.

 

 

 여기서, __introsort_loop에 들어가 봅시다.

 

 

 그러면 __depth_limit == 0인 부분이 있는데요. 만약에 이 조건을 만족하면 __partial_sort로 변환합니다. 이 함수의 내부에는 힙이 들어가 있는데요. 호출 깊이가 깊어지면, heap sort로 변환해서, 복잡도가 O(nlogn)이 되게 하는 것입니다. 이 글에서는 그렇게 중요한 내용이 아닙니다. 왜냐하면, pivot 값인 500과 다른 key 값을 비교하다가 RTE가 떴기 때문입니다.

 

 그러면, partition 과정에서 잘못 되었다는것을 눈치를 챌 수 있는데요. 상식적으로 추론해 보았을 때, 같은 키값과 어떠한 키를 비교하다가 RTE가 떴다면, __unguarded_partition_pivot을 호출했을 때, 문제가 발생했다는 것을 알 수 있어요.

 

 

 이 함수의 내부를 보면 또 2개의 function이 있습니다. __move_median_to_first는, 함수 명을 보아도 알 수 있다시피, 미디안 값을 피벗으로 삼고, 그것과, 정렬할 배열의 처음 원소를 맞바꾸는 역할을 하는 function임을 알 수 있어요. 이것과, RTE는 아무런 연관이 없습니다. 그러면 범인은, 제가 블록을 칠해놓은 __ungarded_partition일 겁니다. 내부로 들어가 봅시다.

 

 

 제가 드래그를 한 부분을 봅시다. __comp(__first, __pivot) 부분입니다. __pivot이 500이였고, __first가 어느 값이였던지 간에 True인 경우가 st.cpp였습니다. 이 경우에는, 계속 ++__first만 증가할 거에요. 그러면, 배열의 인덱스가 벗어나도 계속 그 위치에 접근할 겁니다. 당연하게도 RTE의 원인 중 하나입니다.

 

 

 st2.cpp의 경우, 키1과 키2가 있을 때, 키1의 값이 600이였다면 false였습니다. 500과 600을 비교했을 때, FALSE를 리턴했었습니다. 따라서, while(__comp(__first,__pivot)) 루프가 끝이 나고, 제가 블록을 친 루프에 들어갈 겁니다. 그런데, 피벗이 500이라면 __last가 어떤 값인지 상관 없이 무조건 이 값은 true가 될 겁니다. 따라서, while Loop는 끝나지 않고, __last는 계속 감소할 겁니다. 배열 인덱스에서 벗어났음에도 불구하고요. st2.cpp 또한, RTE가 나는 이유입니다.

 

 키 값 2개를 비교했을 때 무조건 true가 리턴되게 하면 환경에 따라서 RTE가 발생할 수도 있다는 점. 피벗값을 기준으로 탐색하는 과정에서 무한 루프가 걸릴 수도 있다는 점을 챙겨가셨으면 좋겠습니다.