알고리즘 - 9 선택 알고리즘

선택 알고리즘

- n개의 원소가 불규칙하게 저장된 배열에서 i번째 작은 원소(큰 원소)를 찾는 문제를 해결하기 위한 알고리즘

- 정렬과 비슷

- 두 가지 알고리즘

 1. 평균적으로 선형 시간이 소요되는 알고리즘

 2. 최악의 경우에 선형 시간이 소요되는 알고리즘

 

 

 

 

 

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

- 퀵 정렬처럼 분할한 후 자기 호출 방법을 이용하여 평균적으로 선형시간 i번째 작은 원소를 찾는 것

 

배열 A에서 i번째 요소 찾기

- 경우 1. 워소가 하나뿐인 경우 하나 리턴

- 경우 2. 원소가 다수인 경우, 파티션을 통해 중간값이 몇번째인지 확인

- 경우 3. 중간값이 i와 같은 경우, A[파티션을 통해 얻은 중간] 값을 리턴

- 경우 4. 중간 값이 i보다 클 경우, 오른쪽 그룹으로 범위를 좁혀 재귀적으로 실행

- 경우 5. 중간 값이 i보다 작을 겨웅, 왼족 그룹으로 범위를 좁혀 재귀적으로 실행

 

 

평균 선형시간 선택 알고리즘 작동 예

- 2번째 작은 원소 찾기

- 기준 원소를 r이라 지정하고 분할 수행

- 15와 31을 비교, 15와 8을 비교 ... 15를 기준으로 큰 수는 15 뒤 작은 수는 15 앞

- r을 3으로 지정하여 다시 분할 수행

 

 

유사 코드

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);         // 오른쪽 그룹으로 범위를 좁힘
}

 

 

 

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

- 평균 선형 시간 선택 알고리즘의 단점

-> 분할 균형이 맞지 않고, 찾고자 하는 원소가 운나쁘게 큰 그룹에 속하는 일이 반복하는 경우 성능이 보장되지 않음

- 분할 균형이 나빠보여도 일정한 상수비를 유지하면 점근적 복잡도는 항상 Theta(n)이 됨

- 균형을 맞추기 위한 오버헤드가 너무 커져버리면 최악의 경우 선형시간 선택 알고리즘이 될 수 없음.

 

 

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

}

 

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

 

1. 원소들이 한쪽으로 몰리는 경우

- 원/사각형 그룹 -> 3n/10 - 3개의 원소

- M까지 포함하는 경우 -> 3n/10 - 2개

- 이를 제외한 원소들 -> n - (3n/10-2) = 7n/10 + 2

- 최악의 경우 -> 7n/10 + 3 : 3n/10-3

 => 대략 7:3