Algorithm] Quick Select(K번째 숫자 탐색)

Algorithm] Quick Select(K번째 숫자 탐색)

정렬되지 않은 숫자들을 입력 받고 K번째로 작은 숫자를 찾는 방법을 떠올리자면,

가장 먼저 떠오르는 것이 정렬한 후에 바로 접근하는 것을 생각해볼 수 있다.

통상 퀵 정렬이나 합병 정렬을 통해서 정렬을 수행하면 시간 복잡도가 O(nlogn)이고,

이후 탐색에서의 시간 복잡도는 O(1)로 결과적으로 O(nlogn)의 시간 복잡도를 예상해볼 수 있다.

이보다 좀 더 효율적인 것을 찾아볼 수는 없을까?

정렬 중에서 가장 빠른 성능을 보이는, 퀵정렬을 한 번 살펴볼 필요가 있다.

퀵정렬은 피봇(pivot)을 선정하여 피봇을 기준으로 분할한 정보를 또 다시 피봇으로 나누는

분할 정복 과정을 통해서 정렬을 이루는 방법이다.

여기서 이 피봇에 주목할 필요가 있다.

한 번 그 위치가 결정되면 다시는 위치가 바뀔 일이 없다는 점을 주목하자.

분할 과정에서 선택되는 정해지는 피봇은 정렬 결과에서 그것의 절대적인 위치를 뜻한다.

의사코드를 살펴보도록 하자.

QuickSelect(arr, left, right, select)

입력 : arr[left]~arr[right], select(1<=select<=N, N=right-left+1)

출력 : arr에서 select번째 작은 원소

pivot = Partition(arr,left,right)

arr[left]~arr[right]에서 선택하여 피봇을 선정하며,

이 피봇은 퀵정렬의 피봇 선정 과정과 동일한 방식으로 진행된다.

if(pivot-left=select-1)

return arr[pivot] 탐색 성공

else if(pivot-left>select-1)

return QuickSelect(arr,left,pivot-1,select) Small Group에서 탐색 시도

else

return QuickSelect(arr,pivot+1,right,select-pivot+left-1) Large Group에서 탐색 시도

퀵정렬을 구현할 수 있는 사람이라면,

그다지 다른 점을 찾아볼 수 없다.

퀵정렬은 더 이상 분할할 수 없을 때까지 부분문제를 만들어냈던 반면,

이 선택 알고리즘은 원하고자 하는 답인지 판단하는 과정을 거친 후

다시 분할하여 부분문제를 만들어 후보군을 추려내는 형식으로 진행된다.

#include <stdio.h>
#include <stdlib.h>
 
/* Swap */
void Swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
 
/* Partition */
int Partition(int arr[], int left, int right)
{
    // 기본적으로 QuickSort의 Pivot 선정 후 교환 과정과 동일
    // pivot은 가장 왼쪽의 인덱스로 결정
    int pos = arr[left];
    int low = left + 1, high = right;
    while (low <= high)
    {
        while (low <= right && arr[low] <= pos)
        {
            low++;
        }
        while (high >= (left+1) && arr[high] >= pos)
        {
            high--;
        }
        if (low <= high)
        {
            Swap(&arr[low], &arr[high]);
        }
    }
    Swap(&arr[left], &arr[high]);
    return high;
}
 
/* QuickSelect */
int QuickSelect(int arr[], int left, int right, int select)
{
    // 찾고자 하는 인덱스가 범위 내에 존재할 때,
    if (select > 0 && select <= right - left + 1)
    {
        int pos = Partition(arr, left, right);
 
        // 찾고자 하는 숫자를 찾은 경우
        if (pos - left == select - 1)
        {
            return arr[pos];
        }
        // 찾고자 하는 숫자가 small group에 있는 경우
        else if (pos - left > select - 1)
        {
            return QuickSelect(arr, left, pos - 1, select);
        }
        // 찾고자 하는 숫자가 large group에 있는 경우
        else
        { 
            return QuickSelect(arr, pos + 1, right, select - pos + left - 1);
        }
    }
    // 탐색 실패 시,
    return -1;
}
 
int main(void)
{
    int n, index; // n: arr size, k: index
    int *arr = NULL;
 
    printf("배열 크기 : ");
    scanf_s("%d", &n);
    printf("몇 번째 크기의 원소 : ");
    scanf_s("%d", &index);
 
    arr = (int*)malloc(sizeof(int)*n);
 
    printf("배열 입력 : ");
    for (int i = 0; i < n; i++)
    {
        scanf_s("%d", (arr + i));
    }
 
    printf("%d 번째 크기의 원소 : %d\n", index, QuickSelect(arr, 0, n - 1, index));
    return 0;
}