선택 알고리즘 (Selection)

- i번째 작은 수 찾기

- 배열 A [p... r]에서 i번째 작은 원소를 찾는 문제

 

두 가지의 선택(selection) 알고리즘이 존재한다.

1. 평균적으로 선형시간이 소요되는 선택 알고리즘 → select
2. 최악의 경우에도 선형시간이 보장되는 선택 알고리즘 → linearSelect

여기서 선형시간이란, n에 비례하는 시간을 말한다.

<주의> 선택 알고리즘(selection algorithm)은 선택 정렬(selection sort)과는 무관함.

 

작동하는 예를 보면,

작동 예1

 

작동 예2

 

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]; // 기준원소가 바로 찾는 원소임
	else return select(A, q+1, r, i-k); // 오른쪽 그룹으로 범위를 좁힘
} 

평균 수행시간은 T(n)=O(n), 최악의 경우 수행 시간은 T(n)=O(n^2)이 된다.

 

selection algorithm에서 수행시간은 분할의 균형에 영향을 받는다.

- ex) 계속 0:n-1로 분할되고, 찾고자 하는 원소가 운 나쁘게도 큰 그룹에 계속 속한다면 T(n)=O(n^2)이 됨.

---

지금 나올 알고리즘은 최악의 경우, 분할의 균형이 어느 정도 보장되도록 함으로써 수행 시간이 O(n)이 되도록 하는 알고리즘이다. (but, 분할의 균형을 유지하기 위한 오버헤드가 지나치게 크면 안 됨)

 

linearSelect (A, p, r, i)
// 배열 A[p ... r]에서 i번째 작은 원소를 찾는다
{
    ① 원소의 총 수가 5개 이하이면 원하는 원소를 찾고 알고리즘을 끝낸다. 
    ② 전체 원소들을 5개씩의 원소를 가진 개의 그룹으로 나눈다. 
      (원소의 총수가 5의 배수가 아니면 이중 한 그룹은 5개 미만이 된다.)
    ③ 각 그룹에서 중앙값을 (원소가 5개이면 3번째 원소) 찾는다. 
      이렇게 찾은 중앙값들을 m1, m2, …, m(n/5) 이라 하자. 
    ④ m1, m2, …, m(n/5) 들의 중앙값 M을 재귀적으로 구한다. 원소의 총수가
      홀수면 중앙값이 하나이므로 문제가 없고, 원소의 총수가 짝수일
      경우는 두 중앙값 중 아무거나 임의로 선택한다. // call linearSelect( )
    ⑤ M을 기준원소로 삼아 전체 원소를 분할한다. (M보다 작거나 같은 것은
      M의 왼쪽에, M보다 큰 것은 M의 오른쪽에 오도록)
    ⑥ 분할된 두 그룹 중 적합한 쪽을 선택하여 단계 1~6을 재귀적으로
      반복한다.                                  // call linearSelect( )
} 

이 알고리즘은 최악의 경우에도 선형 시간을 보장하기 때문에 O(n)의 시간이 소요된다.

 

 

 

 

 

참고- 쉽게 배우는 알고리즘(개정판)