[Algorithms] Selection Algorithm | 선택 알고리즘

Selection Algorithm

선택 알고리즘

- 입력값들중 \(i\)번째로 작은(큰) 원소를 찾는 알고리즘이다.
- \(n\)개의 입력값들에 대한 전체적인 검색이 필요하기 때문에 \(\Omega(n)\) 만큼의 실행시간이 요구된다.
- 가장 우수한 일반 정렬 알고리즘의 성능이 \(O(n\log n)\)이기 때문에,
  선택 알고리즘의 실행 시간은 적어도 \(O(n\log n)\) 과 같거나 더 우수해야 한다.

Time Complexity: 평균적으로 \(\Theta(n)\), 최악의 경우 \(\Theta(n^2)\) 

---

Background (배경지식)

* Quick Sort (퀵 정렬) (URL)

[Algorithms] Quick Sort | 퀵 정렬

* 퀵 정렬의 \(\texttt{partition(A[], p, r)}\) 함수
- 입력 배열 \(\texttt{A[p...r]}\)에 대하여, 기준 원소를 중심으로 기준값보다 작은 원소들은 왼편에, 큰 원소들은 오른편에 재배치시킨다.
- 기준 원소는 배열 내 어떤 원소도 될 수 있으며, 본 블로그에서는 맨 마지막 원소(\(\texttt{A[r]}\))를 기준원소로 삼는다.
- \(\texttt{partition()}\) 함수는 원소들을 재배치함과 동시에, 기준 원소(\(\texttt{A[r]}\))가 최종적으로 위치하게 되는 인덱스의 값을 리턴한다.
- 최악의 경우(=정렬된 배열을 입력받는 경우)를 그나마 피할 수 있는 방법으로는,
  기준 원소를 매번 랜덤하게 선정하는 방법이 있다. 

---

Mechanism (메커니즘)

- 사용자는 입력 배열 중, \(i\)번째로 큰(작은) 원소의 값을 알고자한다.
- 입력 배열에 대하여, Quick Sort 알고리즘의 \(\texttt{partition()}\) 함수를 한 번 실행시킨다.
- 이 때, \(\texttt{partition()}\) 함수의 리턴값(= 기준 원소의 인덱스)을 통해,
  찾고자 하는 값의 인덱스가 왼쪽 부분 배열에 있는지, 오른쪽 부분 배열에 있는지를 판별할 수 있다.
- 기준 원소의 인덱스가 \(k\)이고, 찾고자 하는 원소의 인덱스가 \(i\)라 할 때,
  \(k < i\) 이면, 찾는 원소는 오른쪽 부분 배열에 있는 것이고,
  \(k > i\) 이면, 찾는 원소는 왼쪽 부분 배열에 있는 것이며,
  \(k == i\) 이면, 찾는 원소는 기준 원소인 것이다.
- 찾는 원소가 속한 부분 배열이 판정되면, 해당 부분 배열에 대해 Selection 알고리즘을 Recursive하게 수행한다.
  (찾는 원소와 기준 원소가 일치할 때 까지, 재귀적으로 원소를 찾아간다.)

---

Implementation (구현)

* Pserudo Code (의사 코드)

partition(A[], p, r);

select(A[], p, r, i) {                   // 배열A[p...r]에서 i번째 작은 원소를 찾는다.
	if (p == r) then return A[p];        // 배열 A의 원소가 하나뿐인 경우
    
    q ← partition(A, p, r);  // Quick Sort 알고리즘의 partition() 함수
    k ← q - p + 1;           // 기준원소A[q]가 범위 내에서 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);         // 찾는 원소가 오른쪽 부분 배열에 있는 경우
}

partition(A[], p, r) {
    x ← A[r];
    i ← p - 1;
    for (j ← p) to (r - 1)
        if (A[j] ≤ x) then A[++i] ↔ A[j];
    
    A[i+1] ↔ A[r];
    return (i + 1);
}

---

Performance Evaluation (알고리즘 성능 평가)

- 선택 알고리즘의 실행 시간은 평균 \(\Theta(n)\), 최악의 경우 \(\Theta(n^2)\)이다.

- \(n\)개의 원소들에 대해, 기준 원소가 \(k\)번째로 작은 원소이면,
  두 부분 배열은 각각 \(k-1\)개의 원소와 \(n-k\)개의 원소로 구성되어 있다.
- 이 때, 선택 알고리즘의 실행 시간 \(T(n)\)은 아래와 같다.

\(T(n) \leq \mathrm{max}[T(k-1), T(n-k)] + \Theta(n)\)
(\(\Theta(n)\)은 Recursion을 제외한 Overhead의 비용이다. \(\texttt{partition()}\) 함수가 Overhead의 대부분을 차지한다.)

- 여기서, 입력 배열은 가능한 모든 경우가 고루 일어난다 가정하면,
  전체 배열에서 기준원소의 순위 \(k\)는 \(1\)부터 \(n\)까지 동일한 확률로 갖게 된다.
- 이 평균 개념을 적용한 \(T(n)\)은 아래와 같다.

\(T(n) \leq {1 \over n}\sum\limits_{k=1}^{n} max[T(k-1), T(n-k)] + \Theta(n)\)
\(\qquad\;\leq {2 \over n} \sum\limits_{k=\lfloor{n \over 2}\rfloor}^{n-1} T(k) + \Theta(n)\)

- \(\lfloor{n \over 2}\rfloor \leq k \leq n\) 인 모든 \(k\)에 대해 \(T(k) \leq ck\)라 귀납적으로 가정하면 식은 아래와 같이 전개된다.

\(T(n) \leq \sum\limits_{k=\lfloor{n \over 2}\rfloor}^{n-1} ck + \Theta(n)\)
\(\qquad\;= {2 \over n}(\sum\limits_{k=1}^{n-1} ck - \sum\limits_{k=1}^{\lfloor{n \over 2}\rfloor - 1} ck) + \Theta(n)\)

\(\qquad\;= {2 \over n}({c(n - 1)n \over 2} - {c(\lfloor{n \over 2}\rfloor - 1)\lfloor{n \over 2}\rfloor \over 2}) + \Theta(n)\)

\(\qquad\;\leq {2c \over n}({(n-1)n \over 2} - {({n \over 2} - 2)({n \over 2} - 1) \over 2}) + \Theta(n)\)

\(\qquad\;= c(n-1) - {c \over n}({n^2 \over 4} - {3n \over 2} + 2) + \Theta(n)\)

\(\qquad\;= cn + (-{cn \over 4} + {c \over 2} - {2c \over n} + \Theta(n)) \qquad *\)

\(\qquad\;\leq cn\)

* 상수 \(c\)를 충분히 크게 잡으면 \(-{cn \over 4}\)이 \(\Theta(n)\)을 압도하여
  \((-{cn \over 4} + {c \over 2} - {2c \over n} + \Theta(n))\) 항을 음수로 만들 수 있으므로, 마지막 단계의 부등식이 성립할 수 있다.

- \(T(n) \leq cn\) 이므로, \(T(n) = O(n)\)이다.
- 또한, 선택 알고리즘의 실행 시간의 상한은 \(\Omega(n)\)이 자명하다.
- 따라서, \(T(n) = \Theta(n)\) 이다.

- 선택 알고리즘의 최악의 경우는 퀵 정렬의 최악의 경우와 같다.
- \(\texttt{partition()}\) 함수의 분할 결과가 항상 \(0 : n-1\)로 도출되며, 찾는 원소가 항상 오른쪽 부분 배열에 속하는 경우이다.
  (꼭, \(0 : n-1\)의 비율이 아니더라도, 이에 준하는 결과가 계속해서 도출되어도 실행 시간은 \(\Theta(n^2)\)에 비례한다.)
- 최악의 경우에 대한 실행 시간 점화식은 아래와 같다.
\(T(n) = T(n-1) + \Theta(n) = \Theta(n^2)\)

---

Reference: 쉽게 배우는 알고리즘 (문병로 저, 한빛아카데미, 2018)