퀵셀렉트

퀵셀렉트(quickselect)는 컴퓨터 과학에서 정렬되지 않은 목록에서 가장 작은 k번째 요소를 찾는 선택 알고리즘이다. 퀵 정렬 알고리즘과 관련이 있다. 퀵 정렬처럼 토니 호어가 개발했으므로 호어의 선택 알고리즘(Hoare's selection algorithm)으로도 부른다. 퀵 정렬처럼 효율적이며 평균적으로 양호한 성능을 내지만 최악의 조건에서는 낮은 성능을 내기도 한다. 퀵셀렉트와 파생 변종들은 실생활의 효율적인 구현체에서 가장 자주 사용되는 선택 알고리즘이다.

 알고리즘 
 // 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)

 각주 

 외부 링크 
 "qselect", Quickselect algorithm in Matlab,  Manolis Lourakis

분류:선택 알고리즘