삽입 정렬

 

삽입 정렬: 각 숫자를 적절한 위치에 삽입하는 정렬 알고리즘.

 

반복적으로 새로운 원소를 이미 정렬된 데이터에 필요할 때만 그 위치를 정해주어 그 곳으로 넣어주는 것이 핵심이다.

 

Ex)

     1 10 5 8 7 6 4 3 2 9

     1 5 10 8 7 6 4 3 2 9

     1 5 8 10 7 6 4 3 2 9

     1 5 7 8 10 6 4 3 2 9

     ~

     1 2 3 4 5 6 7 8 9 10

 

 

시간복잡도 : O(N^2)

삽입 정렬은 앞에 정렬되어 있는 것을 알고있는 상황을 가정하므로 적절한 위치에 삽입만 하기때문에 O(N^2) 정렬 알고리즘 중에서는 효율적인 편임. (거의 정렬된 상태라면 모든 정렬 알고리즘에서도 굉장히 효율적.)

 

Ex) 2 3 4 5 6 7 8 9 10 1

(이미 정렬되어 있으므로 한번씩만 비교하고 마지막 원소 1만 맨 앞으로 삽입되는 연산들을 수행함.)

 

#include <stdio.h>

int main()
{
	int i, j, temp;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
	for(i=0; i<9; i++)
	{
		j=i;
		while(array[j] > array[j+1]) 
		{ // 특정 위치에서 하나씩 감소하며 적절한 위치에 삽입.
		  // 왼쪽에 있는 값보다 더 크거나 같다면 멈춤. (정렬이 되어있다고 가정하므로) 
			temp = array[j];
			array[j] = array[j+1];
			array[j+1]=temp;
			j--;
		} 
	}    
	for(i=0; i<10; i++)
	{
		printf("%d ",array[i]);
	}
	return 0;
}