[Algorithm] 삽입 정렬에 대하여!( Insertion Sort )

안녕하세요. 게임개발자 놀이터 입니다.

이번 포스팅에선 삽입 정렬에 대하여 정리 해보려합니다.

삽입 정렬 ( Insertion Sort )

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입해서 정렬하는 알고리즘 입니다.

삽입 정렬의 경우 첫번째 요소를 이미 정렬됬다. 라고 간주 한 후 정렬을 시작합니다.

정렬되지않은 요소는 목록의 제일 뒤에있는 요소 부터 정렬된 목록과 비교하여 적절한 위치에 삽입합니다.

이 작업을 끝까지 반복하면 모든 요소가 정렬됩니다.

말로만 설명하면 좀 어려울수 있습니다.

정렬 과정

간단하게 삽입 정렬 예시를 보여드리겠습니다.

아래와 같이 5개의 숫자가 주어졌다고 했을때, 삽입 정렬로 정렬 해보겠습니다.

4 9 2 5 7

삽입정렬은 첫번째 요소는 정렬이 되었다고 판단하고, 두번째 부터 시작합니다.

첫번째

4 / □ 2 5 7  | key 값 = 9

9는 4보다 크니까 4보다 뒤쪽에 위치한다. 4 □ 2 5 7 

4 / 9 2 5 7 

두번째

4 9 / □ 5 7 | key 값 = 2

2는 9보다 작으니까 9보다 앞 쪽에 위치한다. 4 □ 9 5 7 

2는 4보다 작으니까 4보다 앞 쪽에 위치한다. □ 4 9 5 7

2 4 / 9 5 7

세번째

2 4 9 / □ 7 | key 값 = 5

5는 9보다 작으니까 9보다 앞쪽에 위치한다. 2 4 □ 9 7

5는 4보다 크니까 4보다 뒤쪽에 위치한다. 2 4 □ 9 7

2 4 5 / 9 7

네번째

2 4 5 9 / □ | key 값 = 7

7은 9보다 작으니까 9보다 앞쪽에 위치한다. 2 4 5 □ 9

7은 5보다 크니까 5보다 뒤쪽에 위치한다. 2 4 5 □ 9

2 4 5 7 9

정렬이 완료 되었습니다.

이처럼 첫번째 값을 제외하고 key 값으로 돌아가며 정렬이 완료된 부분과 비교하며 삽입을 하면 됩니다.

(사진 출처 : 나무위키 삽입정렬)

예제 코드

void InsertionSort(int arrays[], int length)
{
    int key = -1;
 
    for(int i=1; i<length; ++i)
    {
        key = arrays[i]; // 두번째 값부터.
        int j=i-1;
        for(; j>=0; --j)
        {
            if(arrays[j] > key)
            {
                arrays[j+1] = arrays[j];
            }
            else
            {
                break;
            }
        }
        arrays[j+1] = key;
 
    }
}

간단하게 구현했습니다.

알고리즘 분석

비교 횟수

삽입정렬은 두번째 요소부터 첫 요소와 비교하여 정렬한후 세번째 요소는 두번째와 첫번째와 비교합니다.

물론 이미 정렬되어있다면 비교를 하지 않겠지만, 빅오 표기법으로 생각하여 최악의 경우는 전부 비교하는겁니다.

0 + 1 + 2 + 3 .... + n-2 + n-1 = n(n-1)/2 가 되겠군요.

따라서 최악의 경우 시간 복잡도는 O(N²) 가 되겠습니다.

최선의 경우는 비교는 O(1)이고 for문이 Length-1 만큼 돌아야하니 O(n)이겠군요.

밑의 자료는 제가 삽입정렬에 대한 자료를 찾다가 발견한 자료들입니다.

삽입 정렬의 이미지 예시 

( 출처 : 위키 백과 : 삽입 정렬 )

삽입 정렬의 동영상 예시

출처 ( 유투브 동영상(클릭) )

감사합니다.