퀵셀렉트

퀵셀렉트

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

퀵셀렉트(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