티스토리 뷰

최종 수정: 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을 사용하는 것이 좋은 성능을 보임을 알 수 있습니다.

'이론 > Algorithm' 카테고리의 다른 글

Quick Selection을 이용한 O(n) 선택 방법  (6) 2014.03.16
댓글
  • 프로필사진 컴공 안녕하세요 저 STEP의 과정대로 따라가면 5,1,4,3,6 이라고 가정하면
    6,1,4,3,5
    6,1,4,3,5
    6,1,4,3,5
    6,1,3,4,5
    이런 식으로 끝날 것 같은데..제가 잘못 생각했나요?
    2016.10.13 02:39 신고
  • 프로필사진 hackability 제가 아마 http://blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html 이 사이트를 기준으로 글을 썻던것 같은데 이 글에 보면 질문하셧던것처럼 되는것을 피하기 위해 스왑시 조건이 더 달려 있네요

    제가 iteration 관련 조건에 대해 남겨놓질 않아 질문자님께서 생각 하신방식대로 동작을 할것 같습니다. (잘못된 동작)

    기본적인 스탭은 각 Iteration이 돌 때마다 좌측은 배열[mid] 보다 작아야 하고 우측은 배열[mid] 보다 같거나 큰값이 되도록 돌아야 합니다.

    좋은 지적 감사합니다 :)
    2016.10.14 14:44 신고
  • 프로필사진 소프행인 안녕하세요 포스팅 잘 보았습니다^^
    정렬한후 시간계산 그래프는 어떤프로그램을 사용하신건지 궁금하네요...
    2016.10.17 15:23 신고
  • 프로필사진 hackability 엑셀로 작성하여 그림으로 뽑았습니다 :) 2016.11.17 12:36 신고
  • 프로필사진 소프행인 안녕하세요 포스팅 잘 보았습니다^^
    정렬한후 시간계산 그래프는 어떤프로그램을 사용하신건지 궁금하네요...
    2016.10.17 15:23 신고
  • 프로필사진 Dongwoo_SEO 와 감사합니다. 도움이 많이됬네요. 2017.10.03 12:50 신고
댓글쓰기 폼