Quick Selection을 이용한 O(n) 선택 방법

최종 수정: 2014-03-16

안녕하세요. Hackability 입니다.

오늘 포스팅 할 내용은 N 개의 원소에서 k 번째 원소를 선택하는 효율적인 알고리즘에 대해 포스팅 하려고 합니다.

배열 = [5, 1, 4, 3, 2] 라고 되어 있을 때, 2 번째로 큰 값을 찾아라 하는 문제가 주어졌다고 가정합니다. 보통 이런 문제를 풀기 위해 배열을 정렬 (Sorting) 한 뒤, 2번째 값을 참조 하게 됩니다. 하지만 이럴 경우, 궂이 정렬하지 않아도 되는 다른 부분들을 정렬하게 되면서 효율적이지 못하게 됩니다. 

이렇게 k 번째 요소를 선택하는 문제를 해결하기 위해서는 Selection Algorithm을 사용하시는 것이 효율적입니다. 그래서 오늘 소개 드릴 내용은 Quick Selection Algorithm 을 소개 드릴려고 합니다.

Quick Selection은 이름에서도 보시다 싶이, Quick Sort의 원리를 이용하여 만든 알고리즘입니다. 정렬을 한 뒤 k 번째 요소를 찾는 것은 전체 시간 복잡도가 정렬에 따라가기 때문에 worst case 가 O (n log n) 또는 O(n^2)가 됩니다. 하지만 Quick Selection의 경우 worst case 가 O(n) 이 됩니다. 

Quick Selection 동작 원리

배열 = [5, 1, 4, 3, 2]를 이용하여 2번째 작은 값을 찾는 Quick Selection 알고리즘을 살펴 보면 다음과 같습니다.

퀵 정렬과 같이 처음에 Pivot을 중간 값으로 설정합니다. (mid = 2, 배열[mid] = 4)

STEP 1. 

처음에 5는 배열[mid] 보다 크기 때문에 마지막 값과 swap 합니다.

배열 = [2, 1, 4, 3, 5]

STEP 2.

다음 1은 배열[mid] 보다 크지 않기 때문에 다음으로 넘어 갑니다.

배열 = [2, 1, 4, 3, 5]

STEP 3.

다음 배열[mid]는 3보다 크기 때문에 swap합니다.

배열 = [2, 1, 3, 4, 5]

N/2 만큼의 작업으로 우리는 배열[mid] 값을 기준으로 작은 수는 왼쪽 (2, 1, 3), 큰 수는 오른쪽 (5)에 있음을 알 수 있습니다. 우리가 찾아야 하는 값은 2번째 작은 값이므로 배열 = [2, 1, 3] 을 이용하여 다시 위와 같은 작업을 하게 됩니다.

STEP 4.

배열[mid] = 1 이고 2보다 작기 때문에 다음 값을 swap 합니다.

배열 = [1, 2, 3]

이 과정을 반복하게 됩니다. 이 과정을 전체적으로 살펴보면 N번, N/2번, N/4번.... 으로 동작하여 찾게 됩니다. 따라서, 전체 시간을 T(QS) 라 가정하면 동작 시간은 다음과 같이 구할 수 있습니다.

Quick Selection, Quick Sort, Heap Sort 속도 비교

소팅 알고리즘과 비교해서 얼마나 빠른지 비교해봅시다. 비교할 알고리즘은 퀵 소트와 힙 소트 입니다. 테스트 환경은 다음과 같습니다.

데이터 셋은 4 바이트 숫자 100만개, 200만개, 300만개, ..., 1억개 까지 준비 합니다. 숫자는 0 ~ 0xFFFFFFFF 까지 랜덤 값을 넣어서 생성하도록 했습니다.

100만개 부터 1억개 까지 데이터를 생성 시 먼저 용량을 생각해보아야 합니다. 4 byte 숫자 100만개 파일 부터 4byte 숫자 1억개 파일 까지 용량을 계산하기 위해서는 먼저 100만개의 크기를 계산합니다. 100만개의 경우 4B * 1,000,000 = 4,000,000 = 3906.25 KB 의 크기는 갖습니다. 

이를 계산하기 위해 초항은 3906.25 KB, n = 100, 공차(d) = 3906.25 의 등차 수열의 합을 이용하면 됩니다.

-_-;;;;;; 음... 하드에 빈 공간이 많으니 시도해보도록 하겠습니다.

아래는 데이터 셋과 용량 결과 입니다.

계산 결과랑 비슷하게 나왔군요. :D

Quick Selection 알고리즘은 다음과 같이 구현하였습니다. 모든 알고리즘은 추가적인 수정 없이 기본적인 알고리즘으로 비교를 하엿습니다. 또한 좀 더 공정하게 테스트 하기 위해 k를 N/2 로 설정하였습니다.

Quick Selection

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

unsigned int quick_selection(int n, unsigned int *ArrList, int k) {     if (ArrList == NULL || n <= k)         return -1;       int start = 0;     int end      = n - 1;       while (start < end)     {         int i = start;         int j = end;         int mid = ArrList[(i + j)/2];           while (i < j)         {             if(ArrList[i] >= mid)             {                 int tmp = ArrList[j];                 ArrList[j] = ArrList[i];                 ArrList[i] = tmp;                 j--;             } else {                 i++;             }         }           if (ArrList[i] > mid)             i--;           if (k <= i)             end = i;         else             start = i + 1;     }       return ArrList[k]; }

Quick Sort (Wiki 의 기본 소스를 사용)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

void quick_sort (unsigned int *ArrList, int n) {     if (n < 2)         return;       unsigned int p = ArrList[n / 2];     unsigned int *l = ArrList;     unsigned int *r = ArrList + n - 1;       while (l <= r) {         if (*l < p) {             l++;             continue;         }           if (*r > p) {             r--;             continue;         }           unsigned int t = *l;         *l++ = *r;         *r-- = t;     }     quick_sort(ArrList, r - ArrList + 1);     quick_sort(l, ArrList + n - l); }

Heap Sort (Wiki 의 기본 소스에서 k 번째만 찾도록 수정)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

void heap_sort(unsigned int ArrList[], unsigned int cnt, int k)  {     unsigned int t;     unsigned int n = cnt, parent = cnt/2;     unsigned int index, child;       while (1) {          if (parent > 0) {              t = ArrList[--parent];         } else {             n--;                          if (n == cnt-k)                  return;               t = ArrList[n];                     ArrList[n] = ArrList[0];            }                  index = parent;         child = index * 2 + 1;          while (child < n) {                          if (child + 1 < n  &&  ArrList[child + 1] > ArrList[child]) {                 child++;             }                          if (ArrList[child] > t) {                 ArrList[index] = ArrList[child];                 index = child;                 child = index * 2 + 1;             } else {                 break;              }         }           ArrList[index] = t;      } }

속도 비교 결과는 다음과 같습니다. (k = N/2)

X 축은 100만개 ~ 1억개 까지의 데이터이며, Y 축은 계산에 걸린 시간 (sec) 입니다.

정렬의 경우에는 전체 데이터셋을 정렬해야 하기 때문에 확실히 Selection 알고리즘이 좋은 성능을 보임을 확인 할 수 있습니다.

여기서 한 가지 재미있는 것은 Heap Sort와 Quick Sort의 관계인데요. Heap Sort의 경우, Selection 알고리즘 처럼 상위 k 번째 요소를 찾을 수 있도록 설계되어 있습니다. 그런데 왜 Quick Sort 보다 느릴까요? 

이는 k 선택에 있는데 이 실험에서는 k = N/2 로 설정했기 때문에 많은 데이터를 봐야 함으로써 이런 차이가 생겼습니다.

k = 1로 설정했을 때는 다음과 같은 결과를 얻을 수 있습니다.

WOW !

힙 정렬에 놀라운 발전이 생긴것을 볼 수 있습니다. :D

이 결과를 통해 k 가 크지 않다면 힙정렬을 이용하는 것도 나쁘진 않지만 일반적으로 k-th selection 문제에서는 selection algorithm을 사용하는 것이 좋은 성능을 보임을 알 수 있습니다.