[정렬 알고리즘] 01 삽입 정렬(Insertion Sort)이론 및 구현

1. 삽입 정렬 개념

• 손안의 카드를 정렬하는 방법과 유사(새로운 카드를 기존의 정렬된 카드 사이에 올바른 위치에 삽입)
• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입
• key값은 2번째 인덱스부터 시작되며, key값이 자료의 길이만큼 이동되었을 때 정렬이 완성됨

---

2. 삽입 정렬 예제

---

3. 삽입 정렬 특성

1) 장점

• 안정한 정렬 방법(바로 옆의 데이터와 비교하기 때문)
• 자료의 수가 적을 경우 알고리즘 구현이 매우 간단
• 이미 정렬되어 있는 경우나 자료의 수가 적은 정렬에 매우 효율적

2) 단점

• 비교적 많은 레코드들의 이동을 포함
• 자료의 수가 많고 자료의 크기가 클 경우 적합하지 않음

---

4. 삽입 정렬 분석

▶ Pseudo code(의사코드)

* 수행시간은 기본 연산 개수 또는 실행된 "단계"의 횟수
* 가정(Assumption) : $i$행을 실행하는데 $c_{i}$ ($c_{i}$는 상수시간)시간이 걸림
* $t_{j}$는 $j=2, 3, \cdots, n$인 경우에 대해 while루프의 검사가 실행되는 횟수
* 참고 : 주석은 실행되지 않음

① Best Case(배열이 이미 정렬된 경우)

- $j=2,3,\cdots,n$의 각 경우에 대해 $i$가 $j-1$로 초기화될 때, 5행 while문 조건에서 $A[i] \le key$가 됨
- 즉, $t_{j} = 1$이 되어 while문 조건에서 1번 수행하고 while문안의 내용은 수행되지 않음

$c_{i}$들은 상수 $a, b$로 대체 가능하므로 결국 "$an-b$가 된다.

$\therefore$  $O(n)$

② Worst Case(배열이 역순으로 정렬된 경우)

- $j=2,3,\cdots,n$에 대해 $t_{j}=j$가 됨 -> 부분배열 $A[1,...j-1]$과 전부 비교해야 하므로

 

$an^2 + bn + c$로 표현할 수 있음

$\therefore$  $O(n^2)$

---

5. 삽입 정렬 시간 복잡도

1) Best Case(배열이 이미 정렬된 경우)

 ① 비교횟수
   - 이미 정렬되어 있으므로 이동은 없으며 1번의 비교만 이루어짐    
   - 비교횟수 : $(n-1)$번

 ② 시간 복잡도 : $O(n)$

 

2) Worst Case(배열이 역순으로 정렬된 경우)

① 비교횟수
  - 각 반복마다 $i$번의 비교 수행비교
  - 횟수 : $(n-1) + (n-2) + \cdots + 2 + 1 = n(n-1)/2$

② 교환횟수
  - 외부 루프의 각 반복마다 $(i+2)$번의 이동 발생(자료구조가 배열인 경우)
  - $n(n-1)/2 + 2(n-1) = (n^2 + 3n - 4)/2$

③ 시간 복잡도 : $O(n^2)$

 

3) 성능 및 평가

• 보통 $n^2$의 정렬 알고리즘 중 평균적인 성능이 가장 좋은 것으로 알려짐
• 입력 데이터의 정렬 여부에 굉장히 민감
• 바로 옆의 데이터와 비교하기 때문에 안정정렬

	Best	Avg	Worst
삽입 정렬	$O(n)$	$O(n^2)$	$O(n^2)$

---

6. 삽입 정렬 구현(C언어)

#include<stdio.h>

void insertion_sort(int arr[], int length);

int main()
{

	int length;
	int arr[10] = { 10, 28, 30, 2, 15, 8, 67, 45, 3, 11 };

	length = sizeof(arr) / sizeof(int);	

	insertion_sort(arr, length);

	return 0;
}

// 삽입 정렬
void insertion_sort(int arr[], int length) {

	int i, j, key, tmp;

	for (j = 1; j < length; j++) {
		key = arr[j];
		i = j - 1;
		while (i >= 0 && arr[i] >= key) {
			arr[i + 1] = arr[i];
			i = i - 1;
		}
		arr[i + 1] = key; 
	}
}