[40] - Sorting

 이 내용은 algorithm lectures 등지에 출현하는 내용이며 D3D의 기본과 관련성이 다소 떨어질 것 같습니다. 그럼에도 불구하고 Algorithm이기 때문에 <Algorithm> header에 있는 내용이기도 합니다. cppreference 홈페이지에 보면 이렇게 sorting을 위한 Section이 따로 있습니다.

'Sort'라는 이름이 기능 자체를 설명하기 때문에 뭔가 기록할 만한 것이 없습니다. 정렬의 시간 복잡도가 O(Nlog(N))이라는 점은 알아두는 것이 좋습니다. 그리고 Sort는 오름차순으로 정렬을 진행하는 것이 기본값이기 때문에 세 번째 인자에 Functor를 주어서 내림차순으로 만들 수 있습니다.

편리한 함수이기는 하지만 Custom Defined Data Type에 대해서는 비정상적으로 작동할 가능성이 높습니다. 예를 들어서 이전에 작성했던 구조체 ItemType은 less than과 같은 operand가 정의되어 있지 않기 때문에 컴파일 단계에서 오류가 날 것입니다. 이런 상황에서 선택할 수 있는 해결 방법은 크게 두 가지가 있는데 하나는 std::sort의 세 번째 parameter에 적당한 식을 주는 것이고 하나는 필요한 operator를 overload 하는 것입니다.

이 ItemType에 대해서

std::sort를 시도하면

이러한 오류를 얻습니다.

잘 몰라도 operator<에 해당하는 ItemType과 ItemType간의 연산이 불가능하다는 사실 정도는 파악할 수 있습니다. 그래서 첫 번째 해결 방법으로 다음과 같이 작성할 수 있습니다. 오름차순/내림차순 원하는 기준에 따라 식을 달리하면 됩니다.

정수의 내림차순에 따라 정렬이 됐습니다.

구조체의 operator를 overload하는 방법도 있습니다. 사실 이 방법이 더 생산성을 높이는 방법이라고 여겨집니다. 아님 말구요.

std::stable_sort

std::stable_sort라는 것이 존재합니다. 이전에도 partition할 때 order를 흩뜨리지 않고 분할할 수 있는 함수가 Stable의 이름을 달고 있었습니다. 이 std::stable_sort가 흩뜨리지 않는 것은 같은 값을 가진 요소들 사이의 '상대적' 대소관계입니다.

위와 같이 Golf와 Charlie는 123이라는 val을 갖고 있습니다. Sort를 진행하면 이 val을 기준으로 정렬을 할 것이고 이 값이 같으면 Golf, Charlie의 순서가 바뀌지 않을 것입니다. a와 b에 대해서 각각 진행하면 결과는 정말 그렇게 나옵니다.

조금 더 실험을 해보겠습니다. 정말로 이 요소간의 상대적인 대소를 유지시켜주는지 알아봅니다. 아이디어는 이렇습니다. 두 개의 대소가 비교 가능한 요소를 안고 있는 구조체를 만듭니다. 두 개의 서로 다른 벡터에 같은 구조체들의 인스턴스들을 집어 넣고 stable_sort와 sort를 각각 진행하여 같은지 다른지를 보면 됩니다. 대신에 완전히 같은지 아닌지 비교를 진행할 때는 구조체의 두 개의 요소가 모두 같아야 합니다.

그러나, 구조체의 overload operator==()의 조건을 오직 x로만 판단한다면 두 벡터는 정렬 이후에도 같은 값을 가질 것입니다.

두 알고리즘의 차이는 Performace에 있습니다. 대체로 거의 모든 상황에서 Restriction이 적으면 적을 수록 알고리즘 자체에 부여되는 자유도가 높아지며 이에 비례하여 성능이 향상됩니다. 실제로 문서를 참조해보면 두 함수 모두 충분한 메모리 공간이 있다면 O(Nlog(N))의 time complexity를 갖지만 충분한 메모리 공간이 없을 경우엔 std::stable_sort는 O(Nlog^2(N))의 Time Complexity를 갖는다고 명시되어 있습니다. Process를 나눠서 실험해보면 무엇이 빨리 끝나는지 알 수 있을 것입니다. 시스템 프로그래밍 시간에 배웠던 지식이 빛을 보는 순간입니다.

위와 같이 단박에 계산이 불가능 할 만큼 많은 양의 정보를 만들고 Process를 나누어서 실행시켜보고 결과를 관찰합니다. b에 a를 복사하는 과정이 불필요하지만 그냥 했습니다.

눈에 보일 만큼 std::stable_sort()가 느립니다. std::is_sorted라는 함수는 컨테이너에 격납된 요소들의 정렬 여부를 묻는 함수로 언급만 해도 이해가 됩니다. 이 외에도 std::partial_sort라는 함수가 존재하는데 이는 컨테이너에 격납된 일부 요소에 대해 정렬을 진행할 수 있습니다. 또, std::nth_element라는 기묘한 함수가 있습니다.

가령 x { 2, 5, 1, 3, 4 } 라는 컨테이너가 있다고 하고 이를 정렬하면 일반적으로 x' { 1,2,3,4,5 }가 될 것입니다. 그런데 std::nth_element를 사용하기 위해 x의 index 0과 index 4의 iterator, 그리고 nth iterator를 index 2에 각각 넣어주면 nth iterator를 기준으로 좌측과 우측의 값이 나뉘는데 각 그룹의 요소 사이의 상대적인 대소 관계는 보장이 안됩니다. 즉, 일반적인 Sort는 x' { 1,2,3,4,5 }를 보장하지만 이 함수는 { 2,1,3,5,4}를 받을 수 있고 {1,2,3,5,4}를 받는 등 오직 nth iterator에 대해서만 보장을 받는 소름이 끼치는 함수입니다. 이게 왜 필요한지는 모르겠으나 Rank를 결정하는데 사용할 만하기는 한 것 같습니다.