1. 삽입 정렬 (Insertion Sort)
ㅇ 선택한 요소를 순서가 올바른 위치로의 삽입을 반복적으로 수행
ㅇ 특징
- 크기가 작은 정렬 문제에 효율적
- 버블 정렬,선택 정렬과 다음과 같이 차이가 남
. 버블 정렬,선택 정렬이,
.. 아직 정렬되지 않은 배열의 크기를 하나씩 줄여나가는 반면에,
. 삽입 정렬은,
.. `정렬을 끝낸 배열`,`정렬을 해야 할 배열` 2개 그룹으로 구분시키고,
.. 이미 정렬된 배열 크기 1개짜리로 시작하여, 하나씩 늘려나감
- in-place 정렬
- 안정 정렬
ㅇ 계산 효율성
- Worst : O(n2)
. i=1일때 1번,i=2일때 2번,...,i=n-1일때 n-1번
. 따라서, 1+2+...+(n-1) = n(n-1)/2번의 비교 필요
- Best : Ω(n)
. 이미 정렬된 경우
2. 정렬 방법
ㅇ 입력 배열 또는 정렬되지 않은 배열에서 차례대로 원소를 뽑아서,
- 정렬된 배열의 적절한 위치에 삽입하면서, 이를 반복적으로 수행
- 이 과정에서, 삽입된 수 보다 큰 수들은 한칸 씩 우측으로 밀려나감
. 앞쪽 Data[1,..,j-1]은, 정렬된 배열이 되고,
. 뒤쪽 Data[j+1,...,n]은, 아직 미정렬 배열이 됨
ㅇ 2개의 중첩 루프 사용
- 외부 루프는, for 문 사용
. (입력 배열 크기 - 1) 만큼 순환
- 내부 루프는, for 문 또는 while 문 사용
3. 알고리즘 표현
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번째로 키값을 가져옴
}
}