삽입정렬은 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아낸뒤 다시 적당한 곳에

삽입하는 알고리즘 이다.

탐색하는 데이터의 정렬된 앞 부분을 비교해서 자신의 위치에 맞는 곳에 삽입 된다.

평균 소요 시간이 O(n*n)

최악은 역순으로 정렬된 상태.

선택이나 버블에 비해 다소 빠르다.

#include <stdio.h>

void Print_Arr( int arr[] );

void Insert_Sort( int arr[], int size );

void main()

{

int arr[10] = {8,2,12,55,28,39,40,46,100,77};

Print_Arr( arr );

Insert_Sort( arr, 10 );

Print_Arr(arr);

}

void Print_Arr( int arr[] )

{

for( int i = 0 ; i < 10 ; i++ )

{

printf("%d", arr[i] );

if( i < 10 ) printf(" ");

else printf("\n");

}

printf("\n");

}

void Insert_Sort( int arr[], int size )

{

int i, j, key;

for( i = 1 ; i < size ; i++ )

{

key = arr[i];

for( j = i-1 ; j >= 0 ; j-- )

{

if( arr[j] > key ) arr[j+1] = arr[j];

else break;

}

arr[j+1] = key;

}

}