선택 알고리즘 C++ 구현

선택 알고리즘을 C++로 구현해보자.

선택 알고리즘이란, 배열 $ A=[p \dotsb r] $ 에서 $i$번째 작은 원소를 찾는 알고리즘이다.

평균적으로 선형 시간이 소요되는 알고리즘과, 최악의 경우에도 선형 시간이 보장되는 알고리즘 두 가지가 있다. (출처: 문병로, 쉽게 배우는 알고리즘, 한빛아카데미)

 

다음 코드는 평균적으로 선형 시간이 소요되는 알고리즘이다.

퀵 정렬과 굉장히 유사한 방식이다.

 

#include <bits/stdc++.h>
using namespace std;
int a[1000001];
 
int Partition(int x, int y) {
    int s = x, e = x, p = a[y];
    for (; e < y; e++)
        if (a[e] < p) swap(a[s++], a[e]);
    swap(a[s], a[y]);
    return s;
}
 
int select(int x, int y, int i) {
    if (x == y) return a[x];
    int p = Partition(x, y);
    int k = p - x + 1;
    if (k == i) return a[p];
    if (k < i) return select(p + 1, y, i - k);
    else return select(x, p - 1, i);
}
 
int main() {
    int n, k;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> k;
    cout<< select(1, n, k);
}