빠른 선택

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Quick select" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2013년 8월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

빠른 선택

퀵 선택 알고리즘의 애니메이션 시각화.22번째 최소값 선택.
클래스	선택 알고리즘
데이터 구조	배열
최악의 경우 공연	оOV(n2)
베스트 케이스 공연	${\displaystyle \mathrm{\Omega }}$ ${\displaystyle \Oomega$n)
평균 공연	${\displaystyle \mathrm{\theta }}$ ${\displaystyle \Teta$ $\}($n)

컴퓨터 과학에서 퀵선택은 정렬되지 않은 목록에서 k번째 가장 작은 원소를 찾기 위한 선택 알고리즘이다.퀵소트 분류 알고리즘과 관련이 있다.퀵소트처럼 토니 호어(Tony Hoare)에 의해 개발되어 호어(Hoare)의 선택 알고리즘으로도 알려져 있다.^[1]퀵소트처럼 실전에 효율적이고 평균 케이스 성능은 좋으나 최악의 경우 성능이 떨어진다.Quick select와 그 변형은 효율적인 실제 구현에 가장 자주 사용되는 선택 알고리즘이다.

Quickselect는 퀵소트와 동일한 전체적인 접근방식을 사용하며, 하나의 요소를 피벗으로 선택하고 피벗을 기반으로 데이터를 두 개로 분할하여 피벗보다 작거나 더 크다.그러나 퀵소트처럼 양쪽으로 재귀하는 대신 퀵 셀렉트는 한쪽으로만, 즉 찾고 있는 요소가 있는 쪽으로만 재귀한다.이렇게 하면 $\theta {\displaystyle \mathrm{}}$(${\displaystyle n}$ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle \Theta (n\log$ n$)}$에서$$$\theta {\displaystyle \mathrm{}}$(${\displaystyle n}$) ${\displaystyle \Theta (n)}$까지 평균 복잡도가 감소하고 최악의 $경우$는 O (${\displaystyle {n\mathrm{}}^{}}$2${\displaystyle {}^{}}$) ${\displaysty$ O($n^{2$

퀵소트(quicksort)와 마찬가지로 퀵셀렉트(quick selection)는 일반적으로 in-place 알고리즘으로 구현되며, k번째 원소(kth 요소)를 선택하는 것을 넘어 부분적으로 데이터도 정렬한다.정렬과의 연결에 대한 자세한 내용은 선택 알고리즘을 참조하십시오.

알고리즘.

퀵소트에는 부절차라는 것이 있다.partition선형 시간 내에 목록을 그룹화할 수 있는(인덱스에서 범위)left로right)는 두 부분으로 나뉘는데, 특정 요소보다 작은 것과 요소보다 크거나 같은 것이다.다음은 요소에 대한 파티션을 수행하는 유사 코드list[pivotIndex]:

함수 파티션(list, 왼쪽, 오른쪽, pivotIndex)은 pivotValue := list[pivotIndex] 스왑 목록[pivotIndex] 및 list[right] // 피벗을 끝 저장소로 이동색인 :=좌에서 우로 i에 대해 왼쪽 - 1 list[i] pivotValue를 선택한 후 swap list[store]를 선택하십시오.색인] 및 목록[i] 증분 저장소인덱스 스왑 목록[오른쪽] 및 목록[저장소]색인] // 피벗을 최종 위치 반환 저장소로 이동색인

이것은 호아레의 원래 파티션 구성보다 간단하지만 효율성이 떨어지는 로무토 파티션 구성으로 알려져 있다.

퀵소트에서는 두 가지를 재귀적으로 정렬하여 베스트 케이스 $\Omega {\displaystyle \mathrm{}(n}$ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle \Oomega(n\log$ n$)}$회$$ 시간으로 이어진다.그러나, 선택을 할 때, 피벗이 최종 정렬 위치에 있고, 피벗 앞에 있는 모든 사람이 정렬되지 않은 순서로 되어 있고, 그 앞에 있는 모든 사람이 정렬되지 않은 순서로 되어 있기 때문에, 우리는 이미 원하는 요소가 어떤 칸막이 안에 있는지 알고 있다.따라서 한 번의 재귀 호출로 올바른 파티션에서 원하는 요소를 찾을 수 있으며, 이를 바탕으로 빠른 선택을 할 수 있다.

// 왼쪽에서 k번째 가장 작은 목록 요소를 반환한다.우측 포함 // (즉, 좌측 <= k <= 우측>).function select(list, left, right, k) is if left = right then // If the list contains only one element, return list[left]  // return that element     pivotIndex  := ...     // select a pivotIndex between left and right, // e.g., left + floor(rand() % (right − left + 1))     pivotIndex  := partition(list, left, right, pivotIndex)     // The pivot is k = pivotIndex인 경우 최종 정렬된 위치에서 k < pivotIndex인 경우 return list[k] 또는 select(list, 왼쪽, pivotIndex - 1, k) 또는 return select(list, pivotIndex + 1, 오른쪽, k)

---

퀵소트(quicksort)와 유사함을 참고하십시오. 최소 기반 선택 알고리즘이 부분 선택 정렬인 것처럼, 이는 $부분{\displaystyle }$ 퀵소트(partial 퀵소트${\displaystyle )}$로서 O${\displaystyle (n}$) ${\displaystyle O(\log$ $n$$)}$ 파티션의$$$$ O${\displaystyle (}n{\displaystyle }$)만 생성하고 분할한다.이 간단한 시술은 선형적인 성능을 기대해왔으며, 퀵소트처럼 실제로도 상당히 좋은 성능을 가지고 있다.또한 Tail Call 최적화가 가능한 경우 또는 루프를 사용하여 Tail call recursion을 제거할 경우 일정한 메모리 오버헤드만 요구하는 내부 알고리즘이기도 하다.

만약 돌아선 바로 그때 list[ 떠났다]pivotIndex 돌아가 기능 select(목록, 왼쪽, km그리고 4.9초 만 오른쪽)은:=...// 왼쪽 및 오른쪽 pivotIndex 사이에 pivotIndex을 선택합니다:k&lt면 k=pivotIndex 다음 list[k] 다른 돌아오partition(목록, 왼쪽, 오른쪽, pivotIndex)=, pivotIndex 후 바로:)pivotIndex − 1loop.        엘se 왼쪽 := pivotIndex + 1

시간 복잡성

퀵소트처럼 퀵셀렉트는 평균 성능이 좋지만 선택한 피벗에 민감하다.지정된 분수에 따라 검색을 일관되게 감소시키는 선회 피벗을 선택하면 검색 세트의 크기가 기하급수적으로 감소하고 각 단계가 선형이며 전체 시간이 일정 시간(검색 속도에 따라 다름)이기 때문에 성능이 선형임을 알 수 있다.감소하다.그러나 매번 한 요소씩만 감소하는 등 불량 피벗을 일관되게 선택하면 최악의 경우 성능은 $2차{\displaystyle }$: O${\displaystyle ({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$)${\displaystyle }$. ${\displaystyle O(n^{2$})이다$.$$}$ 예를$$ 들어, 집합의 최대 요소를 검색하고 첫 번째 요소를 피벗으로 사용하며 데이터를 정렬하는 경우.최악의 경우 발생할 확률은 $n{\displaystyle }$, ${\displaystyle$ n$,}$과(와) 함께 기하급수적으로 감소하므로$$ 빠른 선택은 거의 확실한 $O{\displaystyle }$(${\displaystyle n}$) ${\displaystyle$ O$(n)}$시간의$$ 복잡성을 갖는다.

변형

가장 쉬운 해결책은 거의 특정한 선형 시간을 산출하는 임의의 피벗을 선택하는 것이다.결정적으로 현실에서 흔히 볼 수 있는 부분 정렬된 데이터에 대해 선형 성능을 산출하는 3중간 피벗 전략(퀵소트처럼)을 사용할 수 있다.그러나, 조작된 시퀀스는 여전히 최악의 경우 복잡성을 야기할 수 있다; David Musser는 그러한 전략에 대한 공격을 가능하게 하는 "Median-of-3 killer" 시퀀스를 묘사하고 있는데, 이것은 그의 장단점 알고리즘의 한 동기였다.

보다 정교한 피벗 전략을 사용하여 최악의 경우에도 선형 성능을 보장할 수 있다. 이는 중위수 알고리즘에서 이루어진다.그러나 피벗 계산의 오버헤드가 높기 때문에 일반적으로 이것은 실제 사용되지는 않는다.빠른 평균 사례 성능과 선형 최악의 경우 성능을 모두 얻기 위해 기본 퀵 선택을 예비 중위수와 결합할 수 있다. 이는 장단위로 이루어진다.

평균 시간 복잡성에 대한 더 미세한 $계산$은${\displaystyle }$n (${\displaystyle 2}$ + ${\displaystyle 2}$ 로그${\displaystyle 2}$2 +${\displaystyle o}$ (${\displaystyle 1}$ )${\displaystyle \mathrm{3\; 3}}$.4${\displaystyle n}$ +${\displaystyle o}$ (${\displaystyle n}$ ) ${\displaystyle n (2+2\log 2+o(1$))의 최악의 경우를 산출한다$.$$\leq 3.4n+o(n)}$ 랜덤 피벗의 경우$$(중앙값의 경우, 다른 k가 더 빠름)^[2]상수는 보다 복잡한 피벗 전략에 의해 3/2로 개선될 수 있으며, 평균 $복잡도$는 1.${\displaystyle \mathrm{5n}}$+ ${\displaystyle \mathrm{\theta }}$(${\displaystyle {}^{}}$ ${\displaystyle {1\mathrm{}}^{}}$/ $)[\displaystyle 1.5n+\]$인 플로이드-리베스트 알고리즘을 산출한다.중위수에 대한$$ $세타(n^{1/2}),$ 다른 k가 더 빠름.

참고 항목

• 플로이드-리베스트 알고리즘
• 인트로셀렉트
• 중위수 중위수

참조

외부 링크

• "q select," Manolis Lourakis, Matlab의 Quickselect 알고리즘