알고리즘...24

선택 알고리즘

n 개의 원소를 가진 정렬되지 않은 집합에서 최소 원소를 찾는 것은 Ω(n)이 소요된다. 더 나아가 i 번째로 작은 원소를 찾을 때 Ο(nlogn)이 소요되는 정렬을 수행 후 i 번째 원소를 찾는다면 Ο(nlogn)이 소요될 것이다.

 

선택 알고리즘은 이러한 문제를 Ο(n)에 가깝게 수행하기 위한 알고리즘이다.

 

평균 선형시간 선택 알고리즘

퀵 정렬의 분할 알고리즘을 이용하여 기준 점 좌측 배열에 원하는 순서의 원소가 존재한다면 좌측 배열에 대해서만 재귀적으로 분할 알고리즘을 적용하여 원하는 위치의 원소를 찾을 수 있게 된다.

 

쉽게 배우는 알고리즘 선택 알고리즘 그림 4-2

 

평균 선형시간 선택 알고리즘

Select(A[], p, r, i)
{
    if (p = r) then
    {
        return A[p];
    }
    q ← Partition(A, p, r);
    k ← q - p + 1;
    if (i < k) then
    {
        return Select(A, p, q - 1, i);
    }
    else if (i = k) then
    {
        return A[q];
    }
    else
    {
        return Select(A, q + 1, r, i - k);
    }
}

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘