[알고리즘]#9_Quick Select

 

1. 개념

 

1. 퀵 셀렉트

퀵 셀렉트는 주어진 배열에서 k째로 작은 원소를 찾는데 활용되는 알고리즘입니다. 퀵 셀렉트 알고리즘은 퀵 정렬과 비슷한 분할-정복 방식을 활용하지만, 주어진 배열을 모두 정렬하는 대신 특정 원소를 찾는 작업에 초점을 맞춥니다. 퀵 셀렉트 알고리즘은 평균적으로 O(n)의 시간 복잡도를 가지며, 최악의 경우 O(n²)의 시간 복잡도를 갖습니다. 최악의 시간 복잡도가 O(n²)인 이유는 퀵 정렬과 같습니다.

 

2. 동작 방식

1. 주어진 배열에서 피벗을 선택합니다.
2. 피벗 원소를 기준으로 배열을 두 개의 부분 배열로 나누고, 피벗 원소보다 작은 원소는 왼쪽 부분 배열로 이동시키고, 반대로 피벗 원소보다 큰 원소는 오른쪽 부분 배열로 이동시킵니다.
3. k(찾고자 하는 k번째 작은 원소의 위치)가 피벗의 위치와 같다면, 이는 k번째 작은 요소가 피벗 원소임을 의미합니다.
4. k가 피벗의 위치보다 작다면, 왼쪽 부분 배열에 대하여 k번째 요소를 찾습니다.
5. k가 피벗의 위치보다 크다면, 오른쪽 부분 배열에서 k-피벗위치-1 번째 원소를 찾습니다.

 

---

 

#2. 코드

 

1. 기본 예제

#include <iostream>
#include <algorithm>
using namespace std;

int partition(int arr[], int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j <= right - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[right]);
    return (i + 1);
}

int quickSelect(int arr[], int left, int right, int k) {
    if (left <= right) {
        int p = partition(arr, left, right); // 피벗 원소 기준으로 정렬
        if (p - left == k - 1) // k가 피벗 위치일 경우
            return arr[p];
        else if (p - left > k - 1) // k가 피벗 위치보다 작을 경우
            return quickSelect(arr, left, p - 1, k);
        else // k가 피벗 위치보다 클 경우, left로부터 + k-p-1 위치가 다음 k가 된다.
            return quickSelect(arr, p + 1, right, k - p + left - 1);
    }
    return INT_MAX; // k가 배열의 범위를 벗어났을 경우
}

int main() {
    int arr[] = {10, 4, 5, 8, 6, 11, 26};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 4; // 4번째로 작은 요소를 찾습니다.
    cout << "k번째로 작은 요소: " << quickSelect(arr, 0, n - 1, k);
    return 0;
}

1. partition 함수를 통해 pivot 기준 왼쪽과 오른쪽 부분 배열을 분할 및 정렬 수행
2. pivot과 k를 비교
3. k가 pivot과 같다면, arr [p]를 반환
4. k가 pivot보다 작다면, left ~ p-1(왼쪽 부분 배열)에서 k 찾기
5. k가 pivot보다 크다면, p+1 ~ right(오른쪽 부분 배열)에서 다음 k(left + k-p-1)를 찾기
* 주의 : k가 pivot보다 클 때, k가 left+k-p-1로 변경됩니다. 왜냐하면, 피벗의 위치는 배열을 분할한 후 피벗이 위치한 배열 내의 인덱스이며, 이는 전체 배열에서의 절대적 위치가 아니기 때문입니다!

 

---