정수 자료형 퀵소트(quick sort) 의 상한선은 O(N log A) 이다.

안녕하세요. 퀵소트 저격 데이터를 만들면서 놀던 pichulia입니다.

 

저는 "잘못 구현한" 퀵소트를 혐오하지만, 잘 구현했다면 그건 인정하는 사람입니다.

 

(참고 : 퀵소트 혐오를 멈출 수 없다. https://hinohie.tistory.com/17 )

퀵소트 저격하기

 

그렇게 퀵소트에 대한 연구(?) 를 그만둔 어느 날, 저에게 새로운 과제거리가 하나 던져졌습니다.

 

문제의 발단

시간복잡도, 또는 수행 시간이 아니라 get / set 횟수를 줄이는 정렬 알고리즘을 구상해보는....

이전에는 생각해 본 적이 없는 고민거리였습니다.

여기에 추가적으로 in-place 정렬이 되어야 하며 (radix sort + merge sort 불가능)

array 는 random access 가 가능한 배열형태이고

데이터는 int 변수라는 추가적인 제약사항까지 얻어왔습니다.

 

in-place 정렬이여야 하기 때문에, 가능한 정렬 알고리즘은 꽤나 제한적이였습니다.

그래서 일단 heap-sort 랑 quick-sort를 실제로 구현해보고 실험을 진행해봤는데..

결론적으로는 퀵소트가 짱이였습니다.

heap sort 탈락

 

물론 데이터가 랜덤하게만 들어온다는 보장이 안되므로, pivot 을 랜덤하게 선택하는 로직이 추가되어야 합니다.

(가장 첫 번째 값을 pivot으로 선택하는 것은 저는 알고리즘으로 인정하지 않습니다.)

 

그러나 이 문제는 연산시간이 아니라 데이터의 get / set 횟수를 줄이는 것이 관건입니다.

set 한 톨도 아껴서 써야하는 판국에, 고정적으로 swap 연산 (== get 2번 + set 2번) 을 사용하는 것이 너무나 아까웠습니다.

swap 을 하는 것이 아깝다.

그래서 이런 횟수를 줄이려고 하다가 문득 이런 생각이 들었습니다.

"pivot 을 꼭 배열의 값 중 하나로 결정해야만 하는걸까?"

---

일반적인 quick sort 에서 pivot 정하고 좌우로 가르는 모습

일반적으로 퀵소트는 배열 안에서 pivot 값을 하나 정한 뒤, 그 값을 기준으로 좌우로 값을 가르는 동작을 취합니다.

여러 방법이 있지만, 일단 제가 알고있는 구현방식으로는...

pivot 값이랑 si 번째 값을 먼저 swap 한 뒤, [si+1 ei) 를 갈라놓고, 좌우로 갈라진 틈에 pivot 을 심어놓는 방식으로 구현합니다.

pivot 을 가상의 숫자로 정하자!

만약 배열 안의 숫자가 전부 정수인걸 알고, 그 안의 수의 범위를 알고있으면 pivot 값을 binary search 로 정해놓고

[si ei) 를 갈라놓을 수 있습니다. 이렇게 갈라놓고 나면 왼쪽의 수들은 pivot 값보다 작거나 같다는 것을 알고 있고, 오른쪽의 수들은 pivot 보다 크거나 같다는 (또는 구현에 따라 pivot 보다 크다는) 것을 알고 있습니다.

그렇게 되면 이제 숫자 범위가 절반씩 줄어들겁니다.

 

이렇게 하면 매번 숫자를 가를 때 마다 수의 범위가 절반씩 줄어들고, 이 때 살펴보는 숫자의 개수는 최대 N 개가 됩니다. 따라서 시간복잡도는 O(N log A) 가 됩니다.

 

말로 적으면 뭔 소린지 모를 가능성도 있으니, 코드를 봅시다. 한쿡말 어려워요 ㅠㅠ

 

void quick_naive(int* const& a, const int& si, const int& ei) noexcept{     int mi = nextint(si, ei-1);     int pivot = a[mi];     swap(a[si], a[mi]);     int i = si + 1;     int j = ei - 1;     while(i<=j)     {       while(i<=j){         if(a[i] <= pivot){i++;}         else{break;}       }       while(j>si){         if(a[j] >= pivot){j--;}         else{break;}       }       if(i>=j)break;       swap(a[i], a[j]);       i++;j--;     }     swap(a[si], a[j]);     quick_naive(a, si, j);     quick_naive(a, i, ei);   }

미사어구 다 빼고 알짜배기만 남긴, 일반적인 quick sort 구현방식입니다. 여기서 주목해야할 것은, i = si + 1; 부터 시작한다는 점이랑, a[j] >= pivot 일 때 j--; 를 수행한다는 점이겠네요.

 

void quick_range(int* const& a, const int& si, const int& ei, const int& minn, const int& maxx) noexcept{     int pivot = ((minn ^ maxx) >> 1) + (minn & maxx);     int i = si;     int j = ei - 1;     while(i<=j)     {       while(i<=j){         if(a[i] <= pivot){i++;}         else{break;}       }       while(j>=si){         if(a[j] > pivot){j--;}         else{break;}       }       if(i>=j)break;       swap(a[i], a[j]);       i++;j--;     }     quick_range(a, si, j + 1, minn, pivot);     quick_range(a, i, ei, pivot+1, maxx);   }

역시나 알짜배기만 남긴, 저의 quick range sort 구현방식입니다. 앞선 quick sort랑 다른 점은, 숫자를 pivot 기준으로 나눌 때의 범위가 [si+1 ei) 가 아니라 [si ei) 라는 점과, a[j] > pivot 일 때 j--; 를 수행한다는 점입니다.

만약 일반적인 구현방법과 마찬가지로 a[j] >= pivot 을 했을 때, 뒤쪽 재귀함수랑 앞쪽 재귀함수에 숫자 범위가 겹치는 부분이 있기 때문에 무한루프가 생길 가능성이 있습니다. (일반적인 구현방법에서는 매 함수마다 최소 1개의 값이 계산범위에서 재외되기 때문에, N^2 만큼의 시간이 걸릴지언정 무한루프에 빠지지 않습니다.)

---

이 게시글도 그렇지만, 언젠간 제 자체 코드들도 어딘가에 정리해놓고 공유하면 좋을 것 같아서

git repo를 하나 팠습니다.

아래는 git에 올린, QuickRangeSort 코드입니다.

 

https://github.com/hinohie/pichulia-archive/tree/main/src/4_QuickRangeSort

GitHub - hinohie/pichulia-archive: private code archive for pichulia

우선은 get/set 횟수를 줄이는 것 자체는 일반적인 상황이 아니니, 일반적인 정렬의 기준처럼 실행시간을 기준으로 측정하도록 코드를 수정해놨습니다.

 

O(N log A) 이니까, 너무나 당연하게도 A 가 작을 땐 꽤나 빠르지만, A 가 커지만 std::sort 보다는 느린 것을 볼 수 있었습니다.

대신에 일반적인 quick sort 보다는 빠르다는 결과가 나왔습니다.