삽입 정렬(insertion sort)

삽입 정렬(insertion sort)은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

즉, 매 순서다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

 

삽입 정렬은 두 번째 자료부터 시작하여 그 앞의 자료들과 비교하여 십입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

 

처음 key 값은 두 번째 요소부터 시작한다.

 

안정된 정렬 방법이며, 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단해서 다른 복잡한 정렬보다 유리할 수 있고, 대부분의 배열이 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

하지만 다른 정렬에 비해 배열들의 이동이 자주 일어나므로, 배열의 크기가 클 경우에 적합하지 않다.

 

#include <stdio.h>
#define SIZE 5

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

int main()
{
	int arr[SIZE]={8,5,6,2,4};
	
	insertion_sort(arr,SIZE);

	for(int i=0;i<SIZE;i++)
		printf("%d ",arr[i]);
	printf("\n");
}

void insertion_sort(int arr[],int n)
{
	int i, j, key;
	
	for(i=1;i<n;i++){
		key=arr[i];

		for(j=i-1 ; j>=0 && arr[j]>key ;j--)
			arr[j+1]=arr[j];

		arr[j+1]=key;
	}
}