삽입 정렬(insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
예제
| 31 | 25 | 12 | 22 | 11 | 처음 상태. | ||
| 31 | [25] | 12 | 22 | 11 | 두 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다. | ||
| <25> | 31 | [12] | 22 | 11 | 세 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다. | ||
| <12> | 25 | 31 | [22] | 11 | 네 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다. | ||
| 12 | <22> | 25 | 31 | [11] | 마지막 원소를 부분 리스트에서 적절한 위치에 삽입한다. | ||
| <11> | 12 | 22 | 25 | 31 | 종료. |
소스 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 | void insertion_sort(int list[], int n) { int key; for (int i = 1; i < n; i++) { key = list[i]; for (int j = i – 1; j >= 0 && list[j] > key; j––) { list[j + 1] = list[j]; } list[j + 1] = key; } } | cs |
특징
그다지 효율이 좋은 정렬 방법은 아니지만, 구현이 쉽다는 장점이 있다.
참조 : 위키백과