Insertion Sort(삽입정렬)

현재 보고 있는 Textbook에서 많은 정렬 알고리즘 중에 가장 처음 나오고 가장 쉬운 정렬 알고리즘이다 

그러나 O(n^2)의 복잡도를 가져서 적은 양의 데이터를 정렬할때 유용하다. 또한 이미 정렬되어 있는 경우 매우 빠르게 동작한다.

간략하게 그림을 통한 예제를 살펴보면,

(이미지 출처 : http://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC)

위의 그림의 설명을 구체적으로 풀어 쓰면,

1) 임의의 수 5개가 있는 수열에서 먼저 두번째 원소를 key값으로 정의한다.

2) 그 key값을 적절한 키의 왼쪽 값들과 비교했을때 왼쪽 값이 key 값 보다 크고, index값이 처음이 아닐때 왼쪽의 값들을 오른쪽으로 한칸씩 이동 한다 

3) 왼쪽 값이 key값 보다 작은 값이 나온 순간 왼쪽 값의 이동을 중단한다.

4) 멈춘 시점의 index보다 한칸 더 큰 위치에 key 값을 위치 시킨다

5) 위의 과정을 마지막 index까지 진행하고 과정을 종료한다.

관련 C 코드는 아래와 같다

#include <stdio.h> void Insertion_sort(int* arr, int length) { int i,j,key; int k; for (i=1; i<length; i++){ key = arr[i]; j = i-1; while (j >= 0 && arr[j] > key){ arr[j+1] = arr[j]; j--; } arr[j+1] = key; } // Sort Results. printf("Result: "); for (k=0; k<length; k++){ printf("%d ", arr[k]); }printf("\n"); } int main() { int length = 5; int arr[length]; int i; printf("Enter the unsorted number: "); for(i=0; i<length; i++){ scanf("%d", &arr[i]); } Insertion_sort(arr, length); return 0; }

위 코드의 실행결과는 아래와 같다