Sort 삽입 정렬(Insertion Sort) 알고리즘

[Sort] 삽입 정렬(Insertion Sort) 알고리즘

 

삽입 정렬은 두 번째 원소부터 시작하여 앞의 원소들을 비교하고, 삽입할 위치를 정한다. 삽입할 위치가 정해졌으면 대상 위치 부터 자신의 바로 앞 위치까지 있는 원소들을 한 칸씩 뒤로 옮겨 들어갈 자리를 만든 후 삽입해 정렬하는 알고리즘이다. 가나다 순으로 되어있는 책들 사이에 끼워 넣거나 순서대로 정렬할 필요가 있는 카드를 생각하면 이해가 쉽다.

 

아래는 삽입 정렬을 그림으로 표현한 것이다.

1회차

   - 2번째 원소 3을 Key로 두고 앞에 있는 5와 비교하고 자리를 바꾼다.

2회차

   - 3번째 원소 1을 Key로 설정하고 앞에있는 5와 3을 비교하고 뒤로 한 칸씩 밀어낸다.

   - 비어있는 첫 번째 원소 자리에 1을 삽입한다.

3회차

   - 4번째 원소 4를 Key로 설정한다.

   - 5와 3을 비교했지만 3은 4보다 작기 때문에 첫번째 원소는 검사하지 않는다.

   - 5를 뒤로 옮기고 4를 3번째 원소 자리에 삽입한다.

4회차

   - 5번째 원소 2를 Key로 설정한다.

   - 앞에 있는 원소들을 차례대로 검사하고 첫 번째 원소를 제외한 나머지 원소들을 뒤로 한 칸씩 옮긴다.

   - 2를 2번째 원소 자리에 삽입한다.

 

 

 

void insertion_Sort(A[], n)
{
	int i, j, key;
	for(i = 1; i < n; i++) // 두 번째 인자부터 시작
    {
    	key = A[i];	// 해당 인덱스를 Key로 설정
        for(j = i-1; j >=0; j--)	// key의 앞에서 부터 인덱스를 줄여가며 검사
        {
        	if(A[j] > key)	// key보다 지금 위치가 클 경우 뒤로 한칸 옮김
            {
            	A[j+1] = A[j];
            }
            else	// key보다 지금 위치가 작거나 같을 경우 반복문을 빠져나감
            {
            	break;
            }
        }
        A[j+1] = key;	// 한칸씩 밀린 자리에 삽입
    }
}

삽입 정렬을 참고용 코드로 작성한 것이다.

 

최악 시간복잡도는 O(n^2)이다.

 

이미 정렬 되어 있는 자료들의 경우 삽입정렬을 이용하면 좋다.