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

 

삽입 정렬은 데이터 집합을 순회 하면서

정렬이 필요한 요소를 뽑아내 이를 다시 적당한 곳에 삽입해가는 알고리즘이다.

 

1. 데이터 집합에서 정렬 대상이 되는 요소들을 선택

   이 정렬 대상은 왼쪽부터 선택해 나가며, 그 범위가 처음에는 2개지만,

   알고리즘 반복 횟수가 늘어날 때마다 1개씩 커진다.

   정렬 대상의 최대 범위는 '데이터 집합의 크기 - 1'이다.

2. 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 가지고 있는지 확인

   그렇지 않으면 정렬 대상에서 뽑고 이 요소가 위치할 적절한 곳을 정렬 대상 내에서 찾는다.

   (적절한 위치는 자신보다 더 작은 요소가 없는 위치를 말함)

3. 뽑은 요소를 삽입할 적절한 곳을 찾았을 때

   정렬 대상 내에서 삽입할 값보다 큰 값을 갖는 모든 요소를

   한 자리씩 오른쪽으로 이동 시키고 새로 생긴 빈자리에 삽입

4. 정렬 완료 될 때까지 반복

 

5

1

6

4

2

3

이 6개의 데이터를 가지고 삽입 정렬을 해보자

 

5

1

6

4

2

3

먼저 5와 1을 비교 해본다.

	1
5		6	4	2	3

	1
	5	6	4	2	3

5보다 1이 작으므로 1을 뽑고 5를 오른쪽으로 이동 시킨다.

1	5	6	4	2	3

5가 이동해서 생긴 빈 자리에 1을 삽입

1	5	6	4	2	3

비교대상을 한 개 더 늘려서 비교해본다.

하지만 옮길 데이터가 없으므로 다음으로 넘어간다.

1	5	6	4	2	3

비교 대상을 하나 더 늘려서 비교 해본다.

			4
1	5	6		2	3

4가 6보다 작으니 4를 뽑아 냅니다.

			4
1		5	6	2	3

4보다 큰 5와 6을 옮겨 버립니다.

1	4	5	6	2	3

빈칸에 4를 삽입합니다.

1	4	5	6	2	3

다음 비교 대상을 가지고 비교해본다.

				2
1	4	5	6		3

2는 6보다 작으므로 2를 뽑아 버린다.

				2
1		4	5	6	3

2보다 큰 4,5,6을 옮겨 버린다.

1	2	4	5	6	3

빈 칸에 2를 삽입합니다.

1	2	4	5	6	3

다음 비교대상을 가지고 비교 해본다

					3
1	2	4	5	6

3은 6보다 작으므로 3을 뽑아 버린다.

					3
1	2		4	5	6

3보다 큰 4,5,6을 옮겨 버린다.

1	2	3	4	5	6

빈칸에 3을 삽입합니다.

 

정렬 대상을 줄여나가는 버블정렬과는 달리 삽입정렬은 정렬 대상을 하나씩 늘려나가는 방식이다.

 

삽입 정렬의 비교 횟수를 계산 해보면 다음과 같다.

비교 횟수는 버블 정렬과 다른 것이 없다.

하지만 버블정렬은 데이터 집합이 정렬 되어있거나 흩어져 있거나 무조건

회를 비교하지만 삽입 정렬은 데이터 집합이 정렬 되어 있는 경우.

한번도 비교를 거치지 않는다.

 

최선의 경우와 최악의 경우에 비교 횟수 평균을 내면 …

 

결론은 버블정렬과 삽입정렬을 비교해 보면 성능은 똑같아 보이지만

평균적으로는 삽입 정렬이 더 나은 성능을 보여준다.

 

main.cpp

#include <iostream>   static const int ARRAY_MIN = 0; static const int ARRAY_MAX = 10;   void InsertionSort(int *Data); void Print(int *Data); int main( ) {     int nData[ ARRAY_MAX ] = { 5, 1, 3, 8, 9, 10, 2, 4, 7 ,6 };     Print(nData);     InsertionSort(nData);     std::cout<<"삽입정렬 완료"<<std::endl;     Print(nData);     return 0; }   void InsertionSort(int *Data) {     int nTemp = 0;       for( int nCount1 = 1; nCount1 < ARRAY_MAX ; ++nCount1 )     {         if( Data[ (nCount1) - 1 ] <= Data[ nCount1 ] )         {//위치 옮길 필요가 없을 시             continue;//그냥 패스         }         else         {             nTemp = Data[ nCount1 ];        //해당 하는 데이터를 임시 보관             for( int nCount2 = 0 ; nCount2 < nCount1 ; ++nCount2 )             {                 if( Data[nCount2] > nTemp )                 {//해당하는 데이터 값보다 큰 값일때.                     memmove( &Data[ (nCount2+1) ] , &Data[ nCount2 ] , sizeof( Data[0] ) * (nCount1 - nCount2) );                     //memmove 메모리의 내용을 이동시키는 함수                     /*첫번째 매개변수 : 원본 데이터가 옮길 새로운 메모리의 주소                     두번째 매개변수 : 원본 데이터가 있는 주소                     세번째 매개변수 : 이동시킬 데이터의 크기(Byte)                     */                     Data[nCount2] = nTemp;                     break;                 }             }         }     } }   void Print(int *Data) {     for( int nCount = 0; ARRAY_MAX > nCount ; ++nCount )     {         std::cout<<nCount<<"번쨰 데이터 : "<<Data[nCount]<<std::endl;     } }

출력 결과