퀵셀렉트

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 알고리즘
3. 시간 복잡도
4. 변형 알고리즘
5. 추가 설명
참조

1. 개요

퀵셀렉트는 목록에서 k번째로 작은 요소를 찾는 선택 알고리즘이다. 퀵 정렬의 분할 방식을 활용하여, 선형 시간 내에 목록을 특정 요소(피벗)보다 작은 요소와 크거나 같은 요소로 나눈다. 퀵 정렬과 달리, 퀵셀렉트는 원하는 요소가 속한 분할만을 재귀적으로 처리하여 평균적으로 O(n)의 시간 복잡도를 가진다. 제자리 알고리즘이며, 꼬리 재귀 최적화를 통해 상수 메모리 공간에서 실행 가능하다. 퀵셀렉트는 피벗 선택에 따라 성능이 달라지며, 최악의 경우 O(n²)의 시간 복잡도를 보일 수 있지만, 다양한 변형 알고리즘을 통해 이를 개선한다.

더 읽어볼만한 페이지

퀵셀렉트
개요
종류	선택 알고리즘
자료 구조	배열
최선 시간 복잡도	O(n)
평균 시간 복잡도	O(n)
최악 시간 복잡도	O(n²)
공간 복잡도	O(1)

2. 알고리즘

퀵 셀렉트는 퀵 정렬과 유사하게 `분할(partition)` 과정을 핵심으로 사용한다. 분할 과정은 목록에서 피벗(pivot)을 선택하고, 피벗보다 작은 요소들을 피벗 앞으로, 큰 요소들을 피벗 뒤로 이동시키는 방식으로 동작한다.^[5]

퀵 정렬은 선형 시간 내에 배열(인덱스 `left`에서 `right`까지의 범위)을 특정 요소(피벗)보다 작은 요소의 부분 배열과 같거나 큰 요소의 부분 배열로 분할(partition)하고, 부분 배열에도 반복적으로 분할 처리를 함으로써 목적 배열을 정렬한다. 퀵 정렬에서는 분할 후 양쪽 범위를 재귀 처리하므로 최상의 시간 복잡도는 $\Omega(n\log n)$ 이다. 그러나 퀵 셀렉트는 목적 요소가 피벗보다 뒤에 있는지 앞에 있는지를 미리 알 수 있기 때문에 정렬과 달리 한쪽 범위만 재귀 호출을 하여, 최종적으로 목적 요소를 올바른 위치에 놓을 수 있다.

퀵 셀렉트는 부분 퀵 정렬이며, $O(n)$ 개의 분할 중 $O(\log n)$ 개만 생성하고 분할한다.

2. 1. 분할 (Partition)

분할 함수는 목록 내에서 피벗(pivot)을 선택하고, 피벗을 기준으로 목록을 두 부분으로 나누는 함수이다. 퀵 정렬에서 사용되는 하위 절차로, 선형 시간 내에 목록(인덱스 `left`에서 `right`까지)을 특정 요소보다 작은 요소와 크거나 같은 요소로 나눌 수 있다.^[5]

다음은 요소 `list[pivotIndex]`를 기준으로 분할을 수행하는 의사 코드이다.

```

'''function''' partition(list, left, right, pivotIndex) '''is'''

pivotValue := list[pivotIndex]

swap list[pivotIndex] and list[right] ''// 피벗을 끝으로 이동''

storeIndex := left

'''for''' i '''from''' left '''to''' right − 1 '''do'''

'''if''' list[i] < pivotValue '''then'''

swap list[storeIndex] and list[i]

increment storeIndex

swap list[right] and list[storeIndex] ''// 피벗을 최종 위치로 이동''

'''return''' storeIndex

```

이는 Lomuto 분할 방식으로 알려져 있으며, Hoare 분할 방식보다 덜 효율적이라고 알려져 있다. 그러나 추측 실행을 고려하면 실제로 로무토 방식이 호어 방식보다 빠른 경우가 있다.^[5]

또한, 호어 방식은 양방향 반복자를 요구하지만, 로무토 방식은 전방향 반복자만 요구한다는 차이점이 있다(예: 단방향 리스트의 정렬).^[5]

2. 2. 퀵 셀렉트 (Quickselect)

퀵 셀렉트는 목록에서 k번째로 작은 요소를 찾는 알고리즘이다. 퀵 정렬과 유사하게 `분할` 함수를 사용하지만, 퀵 정렬과 달리 필요한 부분만 재귀적으로 처리하여 평균적으로 선형 시간 복잡도(O(n))를 가진다.
분할(Partition) 함수:`분할` 함수는 퀵 정렬에서도 사용되는 핵심 함수이다. 주어진 목록에서 피벗(pivot)이라는 기준값을 정하고, 피벗보다 작은 요소들은 피벗의 앞으로, 피벗보다 크거나 같은 요소들은 피벗의 뒤로 이동시킨다. 이 과정이 끝나면 피벗은 최종적으로 정렬된 위치에 있게 된다.^[5]

```

'''function''' partition(list, left, right, pivotIndex) '''is'''

pivotValue := list[pivotIndex]

swap list[pivotIndex] and list[right] ''// 피벗을 끝으로 이동''

storeIndex := left

'''for''' i '''from''' left '''to''' right − 1 '''do'''

'''if''' list[i] < pivotValue '''then'''

swap list[storeIndex] and list[i]

increment storeIndex

swap list[right] and list[storeIndex] ''// 피벗을 최종 위치로 이동''

'''return''' storeIndex

```

이 분할 함수는 Lomuto 분할 방식으로 구현된 것이다. Hoare 분할 방식보다 덜 효율적이지만, 더 간단하다는 장점이 있다.^[5]
퀵 셀렉트(Quickselect) 함수:퀵 셀렉트 함수는 `분할` 함수를 재귀적으로 호출하여 k번째로 작은 요소를 찾는다.

```

'''function''' select(list, left, right, k) '''is'''

'''if''' left = right '''then''' ''// 목록에 요소가 하나만 포함된 경우,''

'''return''' list[left] ''// 해당 요소 반환''

pivotIndex := ... ''// left와 right 사이에서 pivotIndex 선택,''

''// 예시,'' left + floor(rand() % (right − left + 1))

pivotIndex := partition(list, left, right, pivotIndex)

''// 피벗이 최종 정렬 위치에 있습니다''

'''if''' k = pivotIndex '''then'''

'''return''' list[k]

'''else if''' k < pivotIndex '''then'''

'''return''' select(list, left, pivotIndex − 1, k)

'''else'''

'''return''' select(list, pivotIndex + 1, right, k)

```

1. 종료 조건: 만약 `left`와 `right`가 같다면, 즉 목록에 요소가 하나만 남았다면 해당 요소를 반환한다.

2. 피벗 선택: `left`와 `right` 사이에서 피벗 인덱스(`pivotIndex`)를 선택한다.

3. 분할: `partition` 함수를 호출하여 피벗을 기준으로 목록을 분할한다.

4. 재귀 호출:

만약 `k`가 `pivotIndex`와 같다면, 피벗이 k번째로 작은 요소이므로 `list[k]`를 반환한다.
만약 `k`가 `pivotIndex`보다 작다면, k번째로 작은 요소는 피벗의 왼쪽에 있으므로, 왼쪽 부분 목록에 대해 `select` 함수를 재귀적으로 호출한다.
만약 `k`가 `pivotIndex`보다 크다면, k번째로 작은 요소는 피벗의 오른쪽에 있으므로, 오른쪽 부분 목록에 대해 `select` 함수를 재귀적으로 호출한다.

퀵 셀렉트는 평균적으로 선형 시간 안에 완료되며, 제자리 알고리즘이다. 또한 꼬리 재귀 최적화를 통해 상수 메모리 공간에서 실행할 수 있다.

2. 3. 꼬리 재귀 최적화

퀵 셀렉트는 꼬리 재귀 형태로 구현될 수 있다. 퀵 셀렉트는 제자리 알고리즘이며, 꼬리 호출 최적화가 적용되는 경우나, 꼬리 재귀를 루프로 제거하면 상수 메모리 공간에서 실행할 수 있다.^[5]

```

'''function''' select(list, left, right, k) '''is'''

'''loop'''

'''if''' left = right '''then'''

'''return''' list[left]

pivotIndex := ... ''// left와 right 사이에서 pivotIndex 선택''

pivotIndex := partition(list, left, right, pivotIndex)

'''if''' k = pivotIndex '''then'''

'''return''' list[k]

'''else if''' k < pivotIndex '''then'''

right := pivotIndex − 1

'''else'''

left := pivotIndex + 1

```

위 코드는 꼬리 재귀를 루프로 제거한 퀵 셀렉트 구현 예시이다.

3. 시간 복잡도

퀵셀렉트는 평균적으로 O(n)의 시간 복잡도를 가진다. 각 분할 단계는 선형 시간(O(n))이 걸리며, 검색 범위가 평균적으로 절반씩 줄어들어 전체 시간 복잡도는 선형이 된다. 이는 피벗을 기준으로 검색 범위가 효과적으로 줄어들기 때문이다.

하지만 최악의 경우에는 퀵셀렉트의 시간 복잡도가 O(n^2)가 될 수 있다. 이는 피벗이 항상 가장 작거나 가장 큰 요소로 선택되어 검색 범위가 거의 줄어들지 않을 때 발생한다. 예를 들어, 이미 정렬된 배열에서 첫 번째 요소를 계속 피벗으로 선택하는 경우가 이에 해당한다.^[2]

이러한 최악의 경우를 방지하기 위해 개선된 피벗 선택 전략을 사용할 수 있다. 예를 들어, 무작위로 피벗을 선택하면 거의 확실하게 선형 시간을 얻을 수 있다.^[2] 또는, 세 요소(시작, 중간, 끝)의 중앙값을 피벗으로 선택하는 '중앙값-3' 전략을 사용할 수도 있다. 이 방법은 부분적으로 정렬된 데이터에서 좋은 성능을 보인다.^[2]

더욱 정교한 방법으로는 중앙값의 중앙값 알고리즘이 있지만, 피벗 계산에 드는 비용이 커서 실제로는 자주 사용되지 않는다. 대신, 퀵셀렉트를 사용하다가 일정 횟수 이상 재귀 호출이 반복되면 중앙값의 중앙값 알고리즘으로 전환하는 인트로셀렉트와 같은 방법이 사용되기도 한다.^[2]

평균 시간 복잡도를 더 자세히 계산하면, 임의의 피벗을 사용할 경우 $n(2+2\log 2+o(1)) \leq 3.4n + o(n)$ 이하이다(중앙값의 경우).^[3] 플로이드-리베스트 알고리즘은 더 복잡한 피벗 전략을 통해 평균 시간 복잡도를 $1.5 n + O(n^{1/2})$ 까지 개선했다.

4. 변형 알고리즘

퀵셀렉트는 평균적으로 선형 시간 복잡도를 가지지만, 최악의 경우에는 성능이 저하될 수 있다. 이러한 문제를 해결하기 위해 다양한 변형 알고리즘이 개발되었다.

인트로셀렉트(Introselect): 퀵셀렉트와 중앙값의 중앙값 알고리즘을 결합한 알고리즘이다. 퀵셀렉트를 기본으로 사용하다가 재귀 깊이가 일정 수준을 넘어가면 중앙값의 중앙값 알고리즘으로 전환하여 최악의 경우에도 선형 시간 복잡도(O(n))를 보장한다.^[3] 데이비드 머서(David Musser)가 개발했으며, 부분적으로 정렬된 데이터에 대한 "중앙값-3 킬러" 시퀀스와 같은 취약점을 해결한다.^[6]
플로이드-리베스트 알고리즘(Floyd-Rivest algorithm): 더 정교한 피벗 선택 전략을 사용하는 알고리즘이다. 중앙값에 가까운 피벗을 선택하기 위해 샘플링을 사용하며, 평균 시간 복잡도를 1.5n + O(n^1/2)로 개선했다.^[6]

이러한 변형 알고리즘들은 퀵셀렉트의 평균적인 성능을 유지하면서도, 최악의 경우 발생할 수 있는 성능 저하 문제를 해결하여 안정성을 높였다.

5. 추가 설명

퀵 셀렉트는 퀵 정렬과 유사하지만, 정렬이 아닌 선택에 초점을 맞춘 알고리즘이다. 퀵 정렬의 '분할' 절차를 활용하여 목록을 두 부분으로 나누고, 원하는 요소가 속한 부분만 재귀적으로 처리한다. 이 과정을 통해 중앙값, 백분위수 등 순서 통계량을 찾는 데 유용하게 사용될 수 있다.^[5]

퀵 정렬은 선형 시간 내에 배열을 특정 요소(피벗)보다 작은 부분과 크거나 같은 부분으로 분할하고, 이 과정을 반복하여 정렬한다. 퀵 셀렉트는 이 분할 방식을 활용하되, 원하는 요소가 있는 부분만 재귀적으로 처리하여 효율성을 높인다.

퀵 셀렉트의 핵심은 분할 후 목적 요소의 위치를 파악하여 한쪽 부분만 재귀 호출하는 것이다. 이를 통해 불필요한 연산을 줄이고, 평균적으로 선형 시간 내에 원하는 요소를 찾을 수 있다. 또한, 퀵 셀렉트는 제자리 알고리즘이므로 추가적인 메모리 공간을 거의 필요로 하지 않는다. 꼬리 재귀 최적화를 통해 메모리 사용량을 더욱 줄일 수 있다.

참조

_[1] 논문 Algorithm 65: Find
_[2] 논문 Exponential bounds for the running time of a selection algorithm http://luc.devroye.o[...]
_[2] 논문 On the probabilistic worst-case time of 'find' https://luc.devroye.[...]
_[3] 웹사이트 Blum-style analysis of Quickselect https://11011110.git[...] 2007-10-09
_[4] 논문 Algorithm 65: Find
_[5] 웹사이트 Lomuto's comeback https://dlang.org/bl[...] 2020-05-14
_[6] 웹사이트 Blum-style analysis of Quickselect https://11011110.git[...] 2007-10-09
_[7] 논문 Algorithm 65: Find

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com