퀵셀렉트

퀵셀렉트

퀵셀렉트 알고리즘의 애니메이션 시각화. 22번째로 작은 값을 선택하고 있다.
분류	선택 알고리즘
자료 구조	배열
최악 시간복잡도	О(n2)
최선 시간복잡도	${\displaystyle \Omega }$(n)
평균 시간복잡도	${\displaystyle \Theta }$(n)

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

// 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