[알고리즘]11.선택 알고리즘

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

 

<n개의 원소 중 i번째 작은 원소 찾기>

(1) 기준 원소보다 작거나 같은 원소는 기준 원소의 왼쪽 그룹으로 재배치한다.

(2) 기분 원소보다 큰 원소는 기준원소의 오른쪽으로 재배치한다. 

(3) 1,2의 과정에 의해 기준원소가 전체에서 몇 번째 작은 원소인지 알 수 있다.

=> 기준원소 = 전체에서 k번째 작은 원소

(4) i < k  =>  i 는 왼쪽 그룹에 있다.

(5) i = k  => 기준 원소 = i

(6) i <k  => i는 오른쪽 그룹에 있다.

 

select(A,p,r,i)   //배열 A[p...r] 에서 i 번째 작은 원소를 찾는다.
{
	if (p=r) then return A[p];   => 원소가 하나뿐일 경우 i는 반드시 1
    	q <- partition(A,p,r);		
    	k <- q-p+1;	=>k : 기준원소가 전체에서 k번째 작은 원소임
   	if (i<k) then return select(A,p,q-1,i);	=>왼쪽 그룹으로 좁힘
    	else if (i=k) then return A(q);		=> 기준원소 = i
    	else return select (A,q+1,r,i-l);	=> 오른쪽 그룹으로 좁힘
}