Selection Sort
선택 정렬
- 정렬되지 않은 영역에서 가장 큰 원소를 찾아 제자리에 위치시키는 것을 반복한다.
* Comparison Sort Algorithms (비교 정렬 알고리즘)
- Selection Sort (선택 정렬) (URL)
- Bubble Sort (버블 정렬) (URL)
- Insertion Sort (삽입 정렬) (URL)
- Merge Sort (병합 정렬) (URL)
- Quick Sort (퀵 정렬) (URL)
- Heap Sort (힙 정렬) (URL)
Mechanism (메커니즘)
- 배열 \(\texttt{A[1 ... n]}\)*에서 가장 큰 원소를 찾아 배열의 끝자리에 있는 원소 \(\texttt{A[n]}\)과 자리를 맞 바꾼다.(오름차순 정렬의 경우)
- 배열 내 가장 큰 원소가 제자리를 찾은 것이므로(추후 변동 없음), 배열의 맨 끝자리를 제외한 나머지 영역에 대해서 정렬을 계속한다.
* \(\texttt{A[1 ... n]}\) : 배열 \(\texttt{A[1]}, \cdots,\texttt{ A[n]}\)을 간략히 표현한 표기법이다.
Pseudo Code (의사 코드)
selectionSort(A[], n) { // A[1...n]을 정렬한다.
for last ← n downto 2 { // last : 배열의 정렬 대상 영역의 맨 마지막 Index 값
A[1 ... last] 중 가장 큰 수 A[k]를 찾는다;
A[k]와 A[last]의 값을 교환;
}
}- 변수 \(\texttt{last}\)는 정렬할 배열의 맨 마지막 인덱스 값(배열의 크기)으로 초기화되고, 가장 큰 수를 찾아 제자리에 놓을 때마다 1씩 감소하여 최종적으로는 2까지 줄어든다.
- \(\texttt{A[1 ... 2]}\)의 두 원소 중 큰 원소를 \(\texttt{A[2]}\)에 위치시키고 나면 제일 작은 원소는 자동으로 \(\texttt{A[1]}\)에 위치하게 되므로 정렬이 성공적으로 끝나게 된다.
- 단일 원소 배열은 그 자체로 정렬이 완료된 상태이므로, 매개변수 \(\texttt{n}\)(배열의크기)은 2 이상의 정수이어야한다.
* Detailed Pseudo Code (보다 세부적인 의사 코드)
selectionSort(A[], n) {
for last ← n downto 2 {
k ← theLargest(A, last);
A[k] 와 A[last]의 값을 교환;
}
}
theLargest(A[], last) {
largest ← 1;
for i ← 2 to last
if (A[i] > A[last]) then largest ← i;
return largest;
}- 큰 수를 찾는 과정을 보다 세부적으로 표현한 의사 코드이다.
(알고리즘은 애매하지 않은 선에서, 최대한 간명한 것이 좋다.)
Performance Evaluation (알고리즘 성능 평가)
선택 정렬의 수행 시간은 모든 경우에 \(\theta(n^2)\) 이다.
pf) \(\texttt{for}\) 루프는 \(\texttt{n-1}\)회 순환한다.
매 루프마다 부분 배열에서 가장 큰 수를 찾는 작업 시간은 배열의 크기에 정비례한다.
(크기가 \(\texttt{n}\)인 배열에서 가장 큰 수를 찾는데에는, 최악의 경우 \(\texttt{n-1}\)번의 비교작업이 필요하다.)
부분 배열 원소 중 가장 큰 원소와 부분 배열의 끝에 위치한 원소를 단순히 맞 바꾸는 작업시간은 상수시간에 정비례한다.
따라서, 선택 정렬 알고리즘은 부분 배열에서 가장 큰 수를 찾기 위해 다른 원소들과 비교하는 작업에 소요되는 시간이 알고리즘의 실행시간을 좌우한다.
수를 비교하는 총 횟수는 첫 번째 부분 배열(완전한 배열)에서는 \(\texttt{n-1}\)번, 두 번째 부분 배열에서는 \(\texttt{n-2}\)번 ... 마지막 부분 배열은 한 번의 비교가 필요하다.
(어떤 경우에서든지 상관없이, 대소비교는 부분 배열 원소 전체에 행해져야 한다.)
즉, 매 루프 주기마다 해당 부분 배열의 전체 원소들 중 최댓값을 가려내는데 필요한 비교 횟수의 총합은
\((n-1) + (n-2) + \cdots + 2 + 1 = {n(n-1) \over 2}\) 이다.
선택 정렬에서는 비교 횟수가 전체 실행시간을 좌우하므로
즉, 선택 정렬의 Time Complexity(시간 복잡도) = \(\theta(n^2)\)
이다.
Reference: 쉽게 배우는 알고리즘 (문병로 저, 한빛아카데미, 2018)
