4. 선택 알고리즘

선택 알고리즘이란?

n개 중 i번째로 작은 원소를 찾는 알고리즘

 

방법 1

1. 퀵 정렬을 사용해서 pivot 기준으로 작으면 왼쪽, 크면 오른쪽으로 나눈다.

2. 

• pivot의 위치가 i보다 크면 왼쪽 집단에서 다시 퀵 정렬을 수행
• pivot의 위치가 i보다 작으면 오른쪽 집단에서 다시 퀵 정렬을 수행
  • 이때, 오른쪽의 맨 앞의 원소를 0번째라고 하면 i-k째 원소를 찾아야함
• pivot의 위치가 i와 같으면 pivot을 반환

이 방법의 경우 최악의 경우(pivot이 집단의 제일 작거나 큰 값으로 선택됐을 경우)에는 $ \Theta (n^2) $ 의 시간복잡도를 가진다.

 

방법2

1. 원소를 5개씩 그룹으로 만들고 각 그룹의 중간값을 찾는다.                             => $ \Theta (n) $

2. 각 그룹의 중간값의 중간값 M을 찾는다.                                                     => $ T ( \lceil{ n \over 5 }) $

3. M보다 큰 경우는 최소 $ {3 \over 5} x {n \over 2} - 2 = {3n \over 10} - 2 $  

   나머지 경우는 $ n - ({3n \over 10} - 2) = {7n \over 10} + 2 $

   따라서 M보다 큰 값인지 작은 값인지 알 수 없는 경우는 최대 $ {7n \over 10} + 2 $  => $ T({7n \over 10} + 2)

==> 시간 복잡도