빠른 선택 (Quick Select) 알고리즘

빠른 선택 알고리즘은 여러 값이 주어졌을 때 k 번째로 작은 값이나 큰 값을 찾을 매우 유용한 검색 알고리즘인데요. 보통 이럴 때 정렬을 생각하지만 빠른 선택 알고리즘을 이용하면 배열을 정렬하지 않고도 빠르게 해당 원소를 찾을 수 있습니다.

알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝

아이디어

일반적으로 빠른 선택 알고리즘을 설명할 때 빠른 정렬 (Quick Sort) 알고리즘이 빠지지 않는데요. 이 두 알고리즘은 공통적으로 피봇(pivot)이라고 하는 임의의 값을 기준으로 배열을 분할하는 로직을 사용하기 때문입니다.

쉬운 이해를 위해서 다음과 같이 1부터 7까지 총 7개의 숫자가 들어있는 배열에서 2번째로 작은 값을 찾아보도록 하겠습니다.

[1, 3, 2, 5, 7, 6, 4]

배열의 마지막 값인 4를 pivot으로 사용해서 이 배열을 피벗 값보다 작은 값과 비벗 값보다 큰 값으로 양분해보겠습니다.

[1, 3, 2] < 4 < [7, 6, 5]

여기서 우리는 pivot이 인덱스 3에 위치하기 때문에 4번째로 작은 값이라는 것과 2번째로 작은 값은 100%로 pivot 왼쪽 편에 있을 것이라 것을 알 수 있습니다. 따라서 오른 편은 더 이상 신경쓰지 않아도 되겠죠?

[1, 3, 2]

그럼 오른 편을 버리고 왼쪽 편의 배열의 마지막 값인 2를 pivot으로 사용해서 다시 배열을 양분해보겠습니다.

[1] < 2 < [3]

이 번 pivot 값은 인덱스 1에 위치하기 때문에 2번째로 작은 값이라는 것을 알 수 있습니다. 원하던 2번째로 작은 값이 2라는 것을 바로 찾게 되었습니다! 🎉

이와 같이 빠른 선택 알고리즘을 사용하면 검색 범위를 딱 절반은 아니라도 계속해서 줄여나갈 수 있기 때문에 매우 효율적으로 원하는 값을 찾을 수 있습니다.

복잡도

• 빠른 선택 알고리즘의 성능은 퀵 정렬 알고리즘과 마찬가지로 pivot 값을 어떻게 선택하느냐에 따라 좌우됩니다.
• 이상적인 경우에는 pivot 값을 기준으로 정확히 매번 배열이 절반으로 나누어져 시간 복자볻는 O(n)이 됩니다. (n + n/2 + n/4 + n/8 ... = 2n = O(n))
• 연속해서 pivot 값이 가장 작은 값이거나 가장 큰 값이 되어 분할할 때 마다 값들이 한 편으로 크게 치우치게 되어 최악의 경우 O(n^2)의 시간 복잡도를 보일 수 있습니다.
• 배열의 크기가 커지면 커질수록 최악의 경우가 발생할 경우가 적어지므로 평균적으로 O(n)의 시간 복잡도를 가지게 됩니다.

구현

빠른 선택 알고리즘을 사용하여 파이썬으로 배열에서 k 번째로 작은 값을 찾는 함수를 구현해볼까요?

def quick_select(arr, k):
    def select(low, high):
        pivot = partition(low, high)
        if k < pivot:
            return select(low, pivot - 1)
        if k > pivot:
            return select(pivot + 1, high)
        return arr[k]

    def partition(low, high):
        p = low
        for i in range(low, high):
            if arr[i] < arr[high]:
                arr[i], arr[p] = arr[p], arr[i]
                p += 1
        arr[p], arr[high] = arr[high], arr[p]
        return p

    return select(0, len(arr) - 1)