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 | 퀵 정렬
Quick Sort 퀵 정렬 - 퀵 정렬은 고급 정렬 알고리즘 중 평균 성능이 가장 뛰어나서 실무에서 가장 많이 사용되는 알고리즘이다. Time Complexity: 평균적으로 \(\Theta(n\log n)\), 최악의 경우 \(\Theta(n^2)\)..
dad-rock.tistory.com
* 퀵 정렬의 \(\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)
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 | 퀵 정렬
Quick Sort 퀵 정렬 - 퀵 정렬은 고급 정렬 알고리즘 중 평균 성능이 가장 뛰어나서 실무에서 가장 많이 사용되는 알고리즘이다. Time Complexity: 평균적으로 \(\Theta(n\log n)\), 최악의 경우 \(\Theta(n^2)\)..
dad-rock.tistory.com
* 퀵 정렬의 \(\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)
