퀵셀렉트

틀:위키데이터 속성 추적 틀:Infobox Algorithm 퀵셀렉트(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