빠른 선택 알고리즘은 여러 값이 주어졌을 때 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)에 가까워지게 됩니다. - 재귀 함수의 호출 스택의 최대
log2 n까지 깊어질 수 있으므로 공간 복잡도는O(log 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)