05 선택 알고리즘

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

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);
}

quick sort와 비슷한 모양새를 가지고 있다.

평균적으로 $\Theta(n)$의 시간이 소요되지만

최악의 경우 $\Theta(n^2)$의 시간이 소요된다.

 

최악의 경우 선형 시간 선택 알고리즘

linearSelect(A, p, r, i)
{
	1. 원소의 총수가 5개 이하이면 i번째 원소를 찾고 알고리즘을 끝낸다.
	2. 전체 원소를 5개씩 원소를 가진 n/5개의 그룹으로 나눈다.
	3. 각 그룹에서 중앙값을 찾는다.
	이렇게 찾은 중앙값들을 m_1, m_2, ..., m_{n/5}이라 하자.
	4. m_1, m_2, ..., m_{n/5}의 중앙값 M을 재귀적으로 구한다.
	5. M을 기준원소로 삼아 전체 원소를 분할한다.
	6. 분할된 두 그룹 중 적합한 쪽을 선택해 1~6을 재귀적으로 반복한다.
}