배열 분할(Partition) 기법으로 k번째로 작은 요소를 찾는 C++ 프로그램

이 글에서는 배열 분할(Partitioning) 기법을 활용하여 배열에서 k번째로 작은 요소를 찾는 C++ 프로그램을 작성하는 방법을 살펴보겠습니다. 이 방식은 퀵 정렬(Quick Sort)의 분할 과정을 응용한 것으로, 배열 전체를 정렬하지 않고도 원하는 순위의 요소를 효율적으로 찾아낼 수 있다는 장점이 있습니다.

동작 원리

분할 기법의 핵심 아이디어는 다음과 같습니다. 먼저 배열의 마지막 요소를 피벗(pivot)으로 선택하고, 피벗보다 작은 값을 가진 요소들을 모두 왼쪽으로 이동시킵니다. 분할이 완료되면 피벗은 자신이 있어야 할 최종 위치에 자리 잡게 되는데, 이때 피벗의 인덱스가 k-1이라면 해당 요소가 바로 k번째로 작은 값입니다. 만약 피벗의 인덱스가 k-1보다 크다면 왼쪽 부분 배열에서, 작다면 오른쪽 부분 배열에서만 재귀적으로 탐색을 계속합니다.

알고리즘

시작
    CreatePartition() 함수: 배열 a, 하한 l, 상한 h를 인자로 받음
    in := l, pi := h
    i를 l부터 h-1까지 반복:
        만약 a[i] < a[pi]라면
            a[i]와 a[in]의 값을 교환
            in을 1 증가
        루프 종료 후
        a[pi]와 a[in]의 값을 교환
    in 반환
종료

시작
    Partition() 함수:
    인자:
        배열 A, 하한 low, 상한 high, 그리고 k
    함수 본문:
        만약 low < high라면
            p_in := CreatePartition(A, low, high)
            만약 p_in == k-1이라면
                k-1 반환
            아니면 p_in > k-1이라면
                Partition(A, low, p_in - 1, k)
            아니면
                Partition(A, p_in + 1, high, k)
종료

예제 코드

#include<iostream>
using namespace std;
void swap(int *a, int *b) {
    int t;
    t = *a;
    *a = *b;
    *b = t;
}
int CreatePartition(int a[], int l, int h) {
    int pi, in, i;
    in = l;
    pi = h;
    for(i=l; i < h; i++) {
        if(a[i] < a[pi]) {
            swap(&a[i], &a[in]);
            in++;
        }
    }
    swap(&a[pi], &a[in]);
    return in;
}
int Partition(int a[], int low, int high, int k) {
    int p_in;
    if(low < high) {
        p_in = CreatePartition(a, low, high);
        if(p_in == k-1)
            return k-1;
        else if(p_in > k-1)
            Partition(a, low, p_in-1, k);
        else
            Partition(a, p_in+1, high, k);
    }
}
int main() {
    int n, i, k, k_k;
    cout<<"\nEnter the number array elements: ";
    cin>>n;
    int a[n];
    for(i = 0; i < n; i++) {
        cout<<"Enter element "<<i+1<<": ";
        cin>>a[i];
    }
    cout<<"\nEnter the k for the kth smallest element: ";
    cin>>k;
    k_k = Partition(a, 0, n-1, k);
    cout<<"\nThe kth smallest element: "<<a[k_k];
    return 0;
}

실행 결과

Enter the number array elements: 4
Enter element 1: 3
Enter element 2: 2
Enter element 3: 5
Enter element 4: 4
Enter the k for the kth smallest element: 3
The kth smallest element: 4

코드 설명

CreatePartition() 함수는 주어진 범위 내에서 마지막 요소를 피벗으로 삼아, 피벗보다 작은 값들을 앞쪽으로 몰아넣은 뒤 피벗의 최종 위치 인덱스를 반환합니다. Partition() 함수는 이 반환값과 목표 인덱스(k-1)를 비교하여, 일치하면 결과를 반환하고 그렇지 않으면 탐색 범위를 절반씩 좁혀가며 재귀 호출을 수행합니다.

위 실행 결과에서 입력된 배열 {3, 2, 5, 4}에서 세 번째로 작은 값을 요청했을 때, 프로그램은 정렬 순서상 세 번째에 해당하는 4를 정확히 출력하는 것을 확인할 수 있습니다.

시간 복잡도

평균적인 경우 이 알고리즘의 시간 복잡도는 O(n)으로 전체 정렬(O(n log n))보다 효율적입니다. 다만 최악의 경우(이미 정렬된 배열 등)에는 O(n²)까지 늘어날 수 있으며, 무작위 피벗 선택 기법을 적용하면 이러한 위험을 줄일 수 있습니다.