1. 삽입 정렬 (Insertion Sort)
ㅇ 선택한 요소를 순서가 올바른 위치로의 삽입을 반복적으로 수행
2. 삽입 정렬의 방법
ㅇ 정렬되지 않은 배열에서 차례대로 원소를 하나씩 선택하여,
- 정렬된 배열의 적절한 위치에 삽입하는 작업을 반복 수행
ㅇ 삽입 과정에서는,
- 삽입하려는 수보다 큰 수들을 오른쪽으로 한 칸씩 밀어냄
. 앞쪽 Data[1,...,j-1]은, 정렬된 부분,
. 뒤쪽 Data[j+1,...,n]은, 아직 정렬되지 않은 부분
ㅇ 두 개의 중첩 루프 사용
- 외부 루프 : for문으로 전체 배열 (입력 배열 크기 - 1 만큼) 순회
- 내부 루프 : for 또는 while문으로, 삽입 위치 탐색 및 이동
3. 삽입 정렬의 특징
ㅇ 소규모 데이터에 매우 효율적
ㅇ 버블 정렬, 선택 정렬과의 차이점
- 버블 정렬/선택 정렬은, 미정렬 부분의 크기를 점점 줄이는 방식
- 삽입 정렬은, 정렬된 부분을 점점 확장하는 방식
. (`정렬을 끝낸 배열`,`정렬을 해야 할 배열` 2개 그룹으로 구분)
. 처음에는 정렬된 부분이 한 개 요소(arr[0])이고,
. 이후 하나씩 정렬된 영역을 키워감
ㅇ in-place 정렬 : (추가 메모리 불필요)
ㅇ 안정 정렬 : (같은 값의 순서 보존)
4. 삽입 정렬의 계산 효율성
ㅇ Worst (최악) : O(n2)
- 배열이 역순으로 정렬되어 있는 경우
. 각 삽입마다 비교 및 이동이 최대 발생
- i=1일때 1번,i=2일때 2번,...,i=n-1일때 n-1번
. 따라서, 1+2+...+(n-1) = n(n-1)/2번의 비교 필요
ㅇ Best (최선) : Ω(n)
- 배열이 이미 정렬되어 있는 경우
. 내부 반복이 한 번도 실행되지 않음
. 각 원소에 대해 한 번의 비교만 수행
. 내부 이동 없음 (매우 빠름)
ㅇ Average (평균적) : O(n2)
- 데이터가 무작위로 섞여 있는 경우
. 삽입 위치를 찾기 위한 비교와 이동이 절반 정도 발생
5. 삽입 정렬의 알고리즘 표현
Input : 정렬 전 Data[], int n
Output : 정렬 후 Data[]
(배열의 앞부분은 항상 정렬되어 있다는 가정하에, 삽입할 요소를 적절한 위치에 삽입)
void insertionSort (int Data[], int n) {
int i = 0; // i : 삽입할 인덱스
int j = 0; // j : 정렬된 부분에서, 위치 인덱스
int key = 0; // key : 비교할 키값
for (i = 1; i < n; i++) { // 인덱스 0은 이미 정렬되어 제외. n-1회 반복.
key = Data[i]; // 현재 삽입할 키값
for (j = i - 1; j >= 0 && Data[j] > key; j--) {
Data[j+1] = Data[j]; // 정렬된 부분에서, 키값보다 큰 값들을 하나씩 우로 이동
}
Data[j+1] = key; // 올바른 위치(j+1번째)로 해당 키값을 삽입
}
}