선택 알고리즘

선택 알고리즘이란?

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

 - 정렬과 비슷하다고 할 수 있음

 - 두 가지 알고리즘

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

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

 

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

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

- 배열 A에서 i 번째 원소 찾기

 1) 원소가 하나뿐인 경우, 그 하나를 리턴

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

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

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

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

 

ex) 2번째 작은 원소 찾기

 1) 기준원소를 r로 정하여 15가 됨

 2) p와 r을 비교하여 기준원소인 15보다 작은 수는 왼쪽, 큰 수는 오른쪽에 배치

 3) 왼쪽 그룹 중에서 3을 피벗(r)으로 잡고 분할

 4) 8과 11을 비교하여 8이 2번쨰 작은 원소임을 찾음

 

ex) 7번째 작은 원소 찾기

 1) 동일하게 두 그룹으로 분할

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

→ 평균 수행 시간: θ(n)

→ 최악의 경우 수행 시간: θ(n²)

 

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

- 평균 선형시간 선택 알고리즘의 단점으로 최악의 경우 θ(n²)의 시간이 걸리게 됨

 ㄴ 경우1: 계속 1:9로 분할이 디고, 이 중 나쁜 경우로 큰 그룹에서 탐색하는 경우

 ㄴ 경우 2: 계속 1:99로 분할이 되고, 이 중 나쁜 경우로 큰 그룹으로 탐색을 하는 경우

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

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

 

유사코드

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

→ 평균 수행 시간: θ(n)

→ 최악의 경우 수행 시간: θ(n)