[Alogrithm] 삽입 정렬 (Injection Sort)

삽입 정렬 (Injection Sort)

 삽입 정렬은, 한 배열을 '앞 배열'과 '뒷 배열'로 쪼개어 '뒷 배열'의 요소를 정렬된 '앞 배열'에 들어갈 올바른 위치를 찾아 삽입하는 정렬이다. 잘 이해가 되지 않을 수 있으므로, 하나씩 설명을 해보겠다.

 

다음과 같이 주어진 배열이 있다고 하자.

array = [3, 4, 5, 2, 1, 6, 7]

3

4

5

2

1

6

7

정렬 알고리즘 전, 주어진 배열을 다음과 같이 빨간 부분과 파란 부분으로 볼 수 있다.

빨간 부분은 이미 정렬이 된 '앞 배열',

파란 부분은 '앞 배열'에 삽입이 되기 위해 대기하고 있는 '뒷 배열'로 이해하면 좋다.

 

정렬 알고리즘은 '뒷 배열'에 들어있는 첫 번째 원소부터 시작하므로, 전체 배열로 생각하면 두 번째 요소부터 정렬 대상이 된다.

두 번째 원소 '4'는 '앞 배열'의 제일 마지막 원소인 '3'보다 크므로, 이동하지 않고 자리가 결정된다.

3

4

5

2

1

6

7

세 번째 원소 '5'는 '앞 배열'의 제일 마지막 원소인 '4'보다 크므로, 이동하지 않고 자리가 결정된다.

3

4

5

2

1

6

7

네 번째 원소를 보자. '2'는 '앞 배열'의 제일 마지막 원소인 '5'보다 작으므로 앞으로 한 칸 이동한다.

'2'는 그 앞인 '4'보다 작으므로 앞으로 한 칸 더 이동하고,

그 앞인 '3'보다 작으므로 앞으로 한 칸 더 이동한다.

따라서 앞에 아무것도 없거나, 앞의 원소보다 '2'가 더 크다면 이동을 멈추고 자리를 결정한다. 

3

4

2

5

1

6

7

3

2

4

5

1

6

7

2

3

4

5

1

6

7

2

3

4

5

1

6

7

 

이와 같은 과정을 반복하면, 삽입 정렬이 완료된다. 코드를 살펴보자.

 

삽입 정렬 파이썬 코드

 

 

삽입 정렬 자바 코드

 

 

 

삽입 정렬 장단점

 

- 삽입정렬의 장점

Best case의 경우, O(N)이라는 좋은 시간복잡도를 가지고 있다.

비교횟수를 버블정렬에 비해 확연히 줄였다.

이미 정렬된 배열, 크기가 작은 배열에 유용하다.

 

- 삽입정렬의 단점

Worst case의 경우 O(n^2)의 시간 복잡도를 가진다.

데이터의 상태와 크기에 따라 성능의 편차가 심하다.