[Algorithm] 선택 알고리즘(selection algorithm)

---

최소 최대 선택 (Minimum and Maximum Selection)

 

가장 간단하게 배열에서 최대값과 최소값을 찾는 방법은 모든 값을 비교하면서 크면, 혹은 작으면 선택하고, 아니면 넘기는 방식으로, 배열의 크기가 $ n $ 이라 할 때 최대값 혹은 최소값을 찾을 때 $ O(n) $ 의 시간복잡도를 요구한다.

그러나 만약 최대값과 최소값을 한번에 찾으려고 한다면 이를 두 번 반복해야 할텐데 한번에 두 값씩 가져와서 비교하는 방식으로 이를 효율적으로 만들 수 있다. 배열에서 두 값을 가져오고, 이를 큰 값과 작은 값으로 나누고, 큰 값은 기존 최대값과, 작은 값은 기존 최소값과 비교하며 업데이트하는 것이다.

int* find_min_max(int list[], int n) {
    int min = list[0], max = list[0];
    for (int i = 0; i < n - 1; i += 2) {
        int small, large;

        if (list[i] < list[i + 1]) {
            small = list[i];
            large = list[i + 1];
        }
        else {
            small = list[i + 1];
            large = list[i];
        }
        if (small < min) {
            min = small;
        }
        if (large > max) {
            max = large;
        }
    }
    if (n % 2 != 0) {
        if (list[n - 1] < min) {
            min = list[n - 1];
        }
        if (list[n - 1] > max) {
            max = list[n - 1];
        }
    }
    int* minmax = new int[2];
    minmax[0] = min;
    minmax[1] = max;
    return minmax;
}

기존보다 아주 약간 빠르게 동작한다. 기존은 $ 2n $  정도의 시간복잡도를 가졌다면 수정된 방식은 $ \frac{3}{2} n + \alpha $ 정도의 시간복잡도를 가진다.

 

---

퀵 선택 (Quick Selection)

 

임의로 나열된 $ n $ 개의 데이터에서 크기가 $ i $ 번째인 값을 찾아낼 때 가장 간단하게 생각할 수 있는 방법은 값들을 정렬한 후 $ i $ 번째 원소를 선택하는 것이다. 정렬 알고리즘 중 효율적인 방식을 선택하면 $ O(n \log n) $ 의 시간복잡도이므로 이 경우 $ O(n \log n) $ 의 시간복잡도를 가질 것이다. 그러나 이 경우가 과연 효과적일까 의문이 들 수 있다. 찾아야 하는 것은 $ i $ 번째 값 하나인데 굳이 모든 값을 정렬할 필요가 없기 때문이다.

퀵 선택은 분할정복(divide and conquer) 방식인 퀵 정렬(quick sort)의 파티션 함수를 이용한 선택 알고리즘으로 $ i $ 번째 값을 찾을 때 전체를 정렬하고 찾는 것보다 일반적인 경우 효율적이다. 자세히 설명하자면 어떤 배열에 대해 피벗을 기준으로 피벗보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 남긴다. 그리고 피벗값의 순서를 확인한다. 만약 피벗값의 순서가 $ i $ 와 같다면 잘 찾은 것이므로 피벗값을 반환한다. 만약 일치하지 않는다면 두 가지 경우로 나뉜다. 피벗값의 순서가 $ i $ 보다 작다면 오른쪽에서 다시 탐색을 시작하고, 피벗값의 순서가 $ i $ 보다 크다면 왼쪽에서 다시 탐색을 시작한다. 오른쪽에서 탐색을 시작한다면 이미 피벗값보다 큰 값들이 모여있으므로 확실히 피벗값의 위치보다는, 즉 순서상 피벗값 뒤에 있는 값들이다. 따라서 이 값들에서 다시 피벗값을 고르고 다시 피벗값보다 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시켜주고, 피벗값의 순서를 확인하고, 맞으면 반환, 아니라면 다시 분할하는 방식으로 $ i $ 번째 값을 확인하면 된다. 왼쪽 탐색도 마찬가지이다.

int partition(int list[], int left, int right) {
    int pivot = list[left];
    int low = left + 1, high = right - 1;
    while (low <= high) {
        while (low <= right && list[low] < pivot) {
            low++;
        }
        while (high >= left && list[high] > pivot) {
            high--;
        }
        if (low < high) {
            swap(list[low], list[high]);
            low++;
            high--;
        }
    }
    swap(list[left], list[high]);
    return high;
}

int selection_i(int list[], int n, int i) {
    int left = 0, right = n;
    while (true) {
        int pivot_index = partition(list, left, right);
        if (i == pivot_index + 1) {
            return list[pivot_index];
        }
        else if (i < pivot_index + 1) {
            right = pivot_index;
        }
        else {
            left = pivot_index + 1; 
        }
    }
}

이렇게 탐색하면 퀵정렬과 마찬가지로 분할이 불균등한 경우 $ O(n^2) $ 의 시간복잡도를 가져 정렬 후 찾는 방식보다 비효율적으로 보이지만, 평균적인 경우 시간복잡도는 $ O(n) $ 으로 일반적인 상황에서는 굉장히 효율적으로 $ i $ 번째 값을 찾을 수 있다.

 

---

중앙값의 중앙값 (Median of Medians)

 

결국 위 퀵 선택 알고리즘의 문제는 분할 기준이었다. 분할이 비균등하게 이뤄질 경우 분할 자체가 의미없어지기 때문이다. 따라서 분할을 의미있게 하기 위해 대략적인 중앙값을 찾는 알고리즘이 나왔다.

아이디어는 다음과 같다. 먼저 배열 전체를 $5$ 개씩 묶어 분할한다. 그리고 각 묶음에서 중앙값을 찾는다. 각 묶음에서 중앙값을 찾는 시간복잡도는 작아서 영향을 크게 끼치지 않는다고 가정한다. 그리고 다시 그 중앙값들을 묶고 그 중 중앙값을 찾는다.

출처: en.wikipedia.org/

이렇게 피벗값을 선택한다면 적어도 절반 정도의 데이터들에 대해서는 확실하게 피벗값보다 작거나 큰 것을 확인할 수 있다. 위 그림에서 각 $ 5 $ 개 묶음이 아래로 갈수록 큰 값이라 검은 값이 중앙값이고, 묶음들의 중앙값의 정렬에서 선택된 $ x $ 에 대해 왼쪽은 $ x $ 보다 작은 중앙값, 오른쪽은 $ x $ 보다 큰 중앙값이라 해보자. 그렇다면 아래 그림에서 빨간색으로 표시된 부분은 무조건 $ x $ 보다 작고, 파란색으로 표시된 부분은 무조건 $ x $ 보다 크다.

배열을 $ 5 $ 개씩 묶음으로 나누면 묶음의 수가 $ \lfloor n / 5 \rfloor $ 이므로 $ 5 $ 개 중 중앙값을 찾는 시간과 $ \lfloor n / 5 \rfloor $ 개 중 중앙값을 찾는 시간이 기존보다 더 들어가는 대신 분할이 나름 최선을 이뤄진다.

$ n $ 개의 원소 중 최소한 $ 3n / 10 $ 개는 제거 가능하고, 분할이 나름 최선으로 이뤄지기에 재귀 깊이가 $ \log n $ 이하이다. 중앙값을 구하기 위한 것까지 고려하면 시간복잡도 $ T(n) $ 은 다음과 같다.

$$ T(n) = T(n / 5) + T(7n / 10) + O(n) $$

여기서 $ O(n) $ 은 전체 피벗 만들기와 분할에 들어가는 선형 부분이다.

전체를 생각해보면 결과적으로 시간복잡도는 $ O(n) $ 이므로 최악의 경우 $O(n^2) $ 의 시간복잡도를 가지던 퀵 선택 대비 효율적인 알고리즘이 되었다.

int get_median(int arr[], int left, int size) {
    sort(arr + left, arr + left + size);
    return arr[left+size/2];
}

int median_of_medians(int list[], int left, int right) {
    int n = right - left;
    if (n <= 5) {
        return get_median(list, left, n);
    }
    int num_medians = (n + 4) / 5;
    int* medians = new int[num_medians];
    for (int i = 0; i < num_medians; i++) {
        int groupLeft = left + i * 5;
        int groupSize = min(5, right - groupLeft);
        medians[i] = get_median(list, groupLeft, groupSize);
    }
    int pivot = median_of_medians(medians, 0, num_medians);
    delete[] medians;
    return pivot;
}

int partition(int list[], int left, int right) {
    int pivot = list[left];
    int low = left + 1;
    int high = right - 1;
    while (low <= high) {
        while (low <= high && list[low] < pivot) {
            low++;
        }
        while (low <= high && list[high] > pivot) {
            high--;
        }
        if (low < high) {
            swap(list[low], list[high]);
            low++;
            high--;
        }
    }
    swap(list[left], list[high]);
    return high;
}

int selection_i(int list[], int n, int i) {
    int left = 0, right = n;
    while (true) {
        int pivot = median_of_medians(list, left, right);
        for (int j = left; j < right; j++) {
            if (list[j] == pivot) {
                swap(list[left], list[j]);
                break;
            }
        }
        int pivot_index = partition(list, left, right);
        int rank = pivot_index - left + 1;
        if (i == rank) {
            return list[pivot_index];
        }
        else if (i < rank) {
            right = pivot_index;
        }
        else {
            i -= rank;
            left = pivot_index + 1;
        }
    }
}