Quickselect Algorithm

Quickselect Algorithm은 선택 알고리즘 중 하나로, 주어진 배열에서 k번째로 큰(또는 작은) 요소를 찾는 데 사용됩니다.

퀵 셀렉트는 퀵 정렬(Quicksort)에서 사용하는 분할 방식(Partitioning)을 응용하여 목표로 하는 k번째 요소를 빠르게 찾습니다.

작동 방식

---

퀵 정렬과 유사하게 배열을 분할하지만, 정렬과 달리 전체 배열을 정렬하지 않고, k번째 요소만 찾는 데 집중합니다.

1. 피벗 선택 및 분할 :

• 배열의 마지막 요소를 피벗으로 선택합니다.
• Partitioning(분할)을 통해 배열을 피벗을 기준으로 두 부분으로 나눕니다.
  • 피벗보다 큰 값들은 배열의 왼쪽 부분에,
  • 피벗보다 작은 값들은 배열의 오른쪽 부분에 위치하게 됩니다.
• 피벗은 자신의 정확한 위치에 놓이게 됩니다. 이 위치는 배열에서 피벗이 몇 번째로 큰 요소인지 나타냅니다.

2. k번째 요소와의 비교 :

• 분할이 완료된 후, 피벗의 위치가 k와 같은지 비교합니다.

• 피벗의 위치가 정확히 k라면, 피벗이 바로 k번째로 큰 요소입니다.

• 피벗의 위치가 k보다 크다면, 왼쪽 부분 배열에서 k번째 요소를 찾습니다.

• 피벗의 위치가 k보다 작다면, 오른쪽 부분 배열에서 k-k'번째 요소를 찾습니다 (k'는 피벗의 위치).

예시 코드

---

C 언어로 구현된 퀵 셀렉트 알고리즘입니다.

#include <stdio.h>

int partition(int ary[], int left, int right) {
    int pivot = ary[right];  // 마지막 요소를 피벗으로 선택
    int i = left;

    for (int j = left; j < right; j++) {
        if (ary[j] > pivot) {  // 피벗보다 큰 값을 왼쪽으로 이동
            int temp = ary[i];
            ary[i] = ary[j];
            ary[j] = temp;
            i++;
        }
    }

    ary[right] = ary[i];
    ary[i] = pivot;

    return i;
}

int quickselect(int ary[], int left, int right, int k) {
    if (left == right) {
        return ary[left];
    }

    int pivotIndex = partition(ary, left, right);

    if (pivotIndex == k) {
        return ary[pivotIndex];
    } else if (k < pivotIndex) {
        return quickselect(ary, left, pivotIndex - 1, k);
    } else {
        return quickselect(ary, pivotIndex + 1, right, k);
    }
}

int main(void) {
    int ary[] = {10, 40, 30, 20, 50};
    int n = sizeof(ary) / sizeof(ary[0]);
    int k = 2;  // 세 번째로 큰 요소를 찾기 위해 k = 2로 설정

    int kthLargest = quickselect(ary, 0, n - 1, k);

    printf("%d번째로 큰 요소: %d\n", k + 1, kthLargest);

    return 0;
}

1. Partition 함수 :

• 이 함수는 주어진 배열을 피벗을 기준으로 분할합니다.

• 피벗보다 큰 값들은 배열의 왼쪽으로, 작은 값들은 오른쪽으로 이동시킵니다.

• 피벗은 정확히 배열에서 몇 번째로 큰지 위치하게 되며, 그 위치를 반환합니다.

2. Quickselect 함수 :

• 주어진 배열에서 k번째로 큰 요소를 찾습니다.

• 분할 결과 얻어진 피벗의 위치가 k와 일치하면, 그 값을 반환합니다.

• 그렇지 않으면, 배열의 왼쪽 또는 오른쪽 부분에서 다시 퀵 셀렉트를 수행합니다.

• 이 과정은 배열이 완전히 정렬되지 않으면서도 k번째로 큰 요소를 효율적으로 찾도록 해줍니다.

시간 복잡도

---

퀵 셀렉트의 평균 시간 복잡도는 $O(n)$입니다. 이는 퀵 정렬의 평균 시간 복잡도인 $O(n log n)$보다 효율적이며, $k$번째 요소만을 찾는 데 최적화되어 있습니다.
최악의 경우, 분할이 계속해서 한쪽으로 치우치는 경우, 시간 복잡도는 $O(n^2)$이 될 수 있습니다.
이를 방지하기 위해 피벗을 임의로 선택하는 등의 최적화 기법을 사용할 수 있습니다.