퀵셀렉트 문서 원본 보기

{{위키데이터 속성 추적}}
{{Infobox Algorithm
|name=퀵셀렉트
|class=[[선택 알고리즘]]
|image=[[파일:Selecting quickselect frames.gif|Animated visualization of the quickselect algorithm. Selecting the 22st smallest value.]]
|caption=퀵셀렉트 알고리즘의 애니메이션 시각화. 22번째로 작은 값을 선택하고 있다.
|data=[[배열]]
|best-time=<math>\Omega</math>(''n'')
|average-time=<math>\Theta</math>(''n'')
|time=О(''n''<sup>2</sup>)
|space=
|optimal=예
}}
'''퀵셀렉트'''(quickselect)는 [[컴퓨터 과학]]에서 정렬되지 않은 목록에서 가장 작은 k번째 요소를 찾는 [[선택 알고리즘]]이다. [[퀵 정렬]] 알고리즘과 관련이 있다. 퀵 정렬처럼 [[토니 호어]]가 개발했으므로 '''호어의 선택 알고리즘'''(Hoare's selection algorithm)으로도 부른다.<ref>{{저널 인용| last1 = Hoare | title = Algorithm 65: Find | doi = 10.1145/366622.366647 | first1 = C. A. R. | author-link1 = Tony Hoare | journal = [[Communications of the ACM|Comm. ACM]] | volume = 4 | issue = 7 | pages = 321–322 | year = 1961 }}</ref> 퀵 정렬처럼 효율적이며 평균적으로 양호한 성능을 내지만 최악의 조건에서는 낮은 성능을 내기도 한다. 퀵셀렉트와 파생 변종들은 실생활의 효율적인 구현체에서 가장 자주 사용되는 선택 알고리즘이다.

== 알고리즘 ==
 ''// Returns the k-th smallest element of list within left..right inclusive''
 ''// (i.e. left <= k <= right).''
 '''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 in its final sorted position''
     '''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)

== 각주 ==
{{각주}}

== 외부 링크 ==
* "[https://www.mathworks.com/matlabcentral/fileexchange/68947-qselect qselect]", ''Quickselect algorithm in Matlab,''  Manolis Lourakis

[[분류:선택 알고리즘]]