Insertion 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[1 ... n]}\) : 배열 \(\texttt{A[1]}, \cdots,\texttt{ A[n]}\)을 간략히 표현한 표기법이다.
* 삽입 정렬과 Induction(귀납법)의 상관관계
- 배열의 크기가 1인 경우에 성립한다. (배열 정렬이 완료되었다.)
- 배열의 크기기 \(k\)일 때 성립하면 (정렬되어 있다면),
\(k+1\)일 때도 성립한다. (한 개의 원소가 적절히 삽입되어도 배열은 정렬된 상태이다.)
- 3개의 기본적인 정렬 알고리즘 중 삽입 정렬에서 귀납적 성질이 가장 선명히 나타난다.
Pseudo Code (의사 코드)
insertionSort(A[], n) {
for i ← 2 to n {
loc ← (i - 1);
newItem ← A[i];
while ((loc >= 1) and (newItem < A[loc])) {
A[loc+1] ← A[loc];
loc--;
}
A[loc+1] ← newItem;
}
}- 변수 \(\texttt{i}\)는 정렬할 배열(\(\texttt{A[1 ... n]}\))의 두 번째 인덱스 값으로 초기화되고,
변수 \(\texttt{loc}\)는 첫 번째 인덱스 값으로 초기화된다.
- \(\texttt{for}\) 루프 내부 구문들이 전부 수행되었다면, \(\texttt{A[1 ... i-1}\)은 정렬이 되어있는 상태이다.
- \(\texttt{A[i]}\)가 \(\texttt{A[i-1]}\)보다 크다면, \(\texttt{A[i]}\)의 자리는 바뀌지 않는다.
- 그렇지 않다면, \(\texttt{A[i-1]}\)부터 시작해서 왼쪽 방향으로 부분 배열의 원소들을 차례로 훑으면서
\(\texttt{A[i]}\)가 들어갈 자리를 찾는다.
- \(\texttt{A[i]}\)가 들어갈 자리부터 이후의 모든 원소들은 한 칸씩 오른쪽으로 밀려나게 된다.
Performance Evaluation (알고리즘 성능 평가)
삽입 정렬의 수행 시간은 최악의 경우에 \(\theta(n^2)\) 이다.
pf) \(\texttt{for}\) 루프는 \(\texttt{n-1}\)회 순환한다.
\(\texttt{while}\) 루프는 최대 \(\texttt{i-1}\)회(최악의 경우) 순환한다.
따라서, 부분 배열에 새로 추가된 원소가 제자리를 찾기까지 최대로 비교하는(최악의 경우) 횟수의 총합은
\((n-1) + (n-2) + \cdots + 2 + 1 = {n(n-1) \over 2}\) 이다.
삽입 정렬에서는 비교 횟수가 전체 실행시간을 좌우하므로,
삽입 정렬의 Time Complexity(시간 복잡도) = \(\theta(n^2)\)
이다.
※ 삽입 정렬은 \(O(n^2)\)의 시간이 드는 비효율적인 정렬 알고리즘군에 속하지만,
배열이 거의 정렬되어 있는 상태로 입력되는 경우에 한해서는 가장 매력적인 알고리즘이다.
Reference: 쉽게 배우는 알고리즘 (문병로 저, 한빛아카데미, 2018)
