[Algorithm/C++] 퀵 선택(Quick Select) - N 번째 수 구하기

 

 

1. 설명

퀵 선택(Quick Select)이란 퀵 정렬을 응용하여 리스트를 정렬하지 않아도 리스트에서 N번 째 작은 값 혹은 큰 값을 구하는 방법이다.

 

 

퀵 정렬이란 분할과 재귀를 사용하여 빠르게 정렬을 할 수 있는 방법으로 자세한 내용은 아래 글을 참고하면 된다.

 

 

[Algorithm/C++] 퀵 정렬(Quick Sort) - 분할과 재귀

 

 

앞서 퀵 정렬을 응용한다고 하였지만 정확하게 말하자면 퀵 정렬을 수행하는 것은 아니다.

 

오히려 퀵 정렬이라기보다는 이진 검색을 하는 방법과 유사한 방법으로 원하는 값을 탐색하는 것이다.

 

 

 

 

먼저 이진 검색을 간단하게 설명하자면 업다운 게임을 예로 들 수 있을 것 같다. 

 

업다운 게임은 1~100 사이 임의의 수를 맞추는 게임으로서 50을 말했을 때 임의의 수가 50보다 낮을 경우 다운, 50보다 높을 경우 업을 말하며 이 과정을 반복하여 임의의 수를 맞추는 것이다.

 

여기서 주목할 점은 처음에 1과 100의 중간 수인 50을 말함으로써 경우의 수를 절반으로 줄인 것이며 다운일 경우, 다음으로 1과 50의 중간인 25를 말하면 또 경우의 수를 절반으로 줄일 수 있게 된다.

 

만약 임의의 수가 25였다면 단 2번만으로 임의의 수를 맞출 수 있으며 1부터 100까지 순차적으로 숫자를 말했을 경우에는 25번 만의 맞추기 때문에 매우 효율적이라고 할 수 있다.

 

 

 

 

그럼 이 이진 검색과 퀵 정렬이 무슨 관계냐고 하면 퀵 정렬은 pivot의 index가 정해지면 pivot 위치보다 왼쪽은 pivot 값보다 낮은 값들이며 pivot보다 오른쪽은 pivot 값보다 높은 값들로 이루어지게 된다.

 

 

즉, pivot은 이미 정렬이 된 상태로서 pivot_index를 보면 pivot이 리스트에서 몇 번째로 큰 수인지를 알 수 있게 된다.

 

그러면 만약 원하는 N번 째 수가 pivot의 위치와 일치하면 pivot의 값이 N번 째 수가 되며, N이 pivot보다 작은 수라면 pivot보다 N번 째 수는 pivot보다 왼쪽의 위치한 것이기 때문에 pivot보다 오른쪽의 경우는 재귀를 수행할 필요가 없는 것이다.

 

 

이처럼 퀵 정렬(Quick Sort)이 정렬을 위해서 pivot 기준 양옆을 재귀로 다시 수행해주었다면 퀵 선택(Quick Select) 한쪽에서만 재귀를 수행하여 N번 째 큰 수를 구할 수 있게 되는 것이다.

 

 

 

특징

▶퀵 선택(Quick Select)의 시간 복잡도는 O(N)으로서 퀵 정렬의 O(N log N) 보다 더욱 효율적이다.

N번 째 큰 수를 구하기 위해서는 퀵 정렬을 수행하고, 정렬된 리스트의 위치 값을 사용할 수도 있지만 N번 째 큰 수 하나만을 구하기 위해서는 이처럼 퀵 선택(Quick Select)을 사용하는 게 더욱 효율적이다.

 

 

 

 

2. 코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <iostream>
using namespace std;

void print(string s);
int quick_select(int n, int left, int right);
void quick_sort(int left, int right);
int partition(int left, int right);
vector<int> v = { 1, 7, 4, 3, 2, 9, 4 };

int main() {
    int n = 6;
    int num = quick_select(n - 1, 0, v.size() - 1);    
    cout << n << " 번째 수 : " << num << "\n";

    quick_sort(0, v.size() - 1);
    print("Quick Sort");

    return 0;
}

int quick_select(int n, int left, int right) {
    if (left >= right) return v[left];

    int pivot_index = partition(left, right);

    if (n < pivot_index) quick_select(n, left, pivot_index - 1);
    else if (n > pivot_index) quick_select(n, pivot_index + 1, right);
    else return v[pivot_index];
}

void print(string s) {
    cout << s << " : ";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << "\n";
}

void quick_sort(int left, int right) {
    if (left >= right) return;

    int pivot = partition(left, right);

    quick_sort(left, pivot - 1);
    quick_sort(pivot + 1, right);
}

int partition(int left, int right) {
    int pivot = v[right];
    int pivot_index = right;

    right--;

    while (1) {
        while (v[left] < pivot) left++;
        while (v[right] > pivot) right--;

        if (left >= right) break;
        else {
            swap(v[left], v[right]);
            left++;
        }
    }
    swap(v[left], v[pivot_index]);
    
    return left;
}

 

결과

 

 

● quick_select 함수

 

1. 형태를 보면 퀵 정렬 함수(quick_sort)와 유사한 것을 볼 수 있다.

 

2. 다만 재귀를 호출할 때 N번 째 수를 구하는 것이므로 pivot_index이 N번 째 수라면 return 해주고 N번 째가 pivot_index보다 작을 경우 pivot_index의 왼쪽 부분만을 재귀해준다.

 

3. 반대로 N번 째가 pivot_index보다 클 경우 pivot_index의 오른쪽 부분만 재귀를 수행함으로써 리스트에서 N번 째 수를 구할 수 있게 된다.

 

 

 

 

● quick_sort, partition 함수

 

퀵 정렬의 사용한 함수들로서 위의 이전의 작성하였던 퀵 정렬 글을 참고하세요.