삽입 정렬

개요

삽입 정렬_{Insertion Sort}이란 정렬된 부분에 정렬되지 않은 데이터를 삽입하여 정렬하는 알고리즘이다. 선택 정렬과 함께 인간에게 뭔가를 정렬하라고 하면 무의식적으로 사용하는 대표적인 알고리즘¹이라고 하는데, 카드 게임을 할 때를 생각해보면 쉽다. 손안의 카드를 정렬하는 방법과 유사하기 때문.

동작

삽입 정렬은 정렬되어 있는 리스트에 새로운 데이터를 적절한 위치에 삽입하는 과정을 반복한다. 선택 정렬과 유사하게, 정렬된 부분과 정렬되지 않은 부분으로 나누어서 사용한다. 이하 과정은 오름차순 정렬의 경우이다.

• 첫 번째 데이터는 이미 정렬된 것으로 가정.

1. 정렬되지 않은 부분의 데이터 선택
2. 선택한 데이터를 정렬된 부분의 데이터와 비교
   • 이 때, 정렬된 부분의 데이터를 역순으로 비교한다.
     • 정렬된 부분의 데이터 중 가장 큰 값부터 비교하기 시작한다는 뜻.
   • 비교 대상이 선택한 데이터(key)보다 클 경우: 해당 데이터를 뒤로 이동
   • 비교 대상이 선택한 데이터(key)보다 작거나 같을 경우: 그 다음 위치에 선택한 데이터 삽입

• 이 과정을 모든 데이터에 대해 반복.

시간 복잡도

• 최선의 경우: $O(n)$
• 최악의 경우: $O(n^2)$
• 평균적인 경우: $O(n^2)$

분석

최선의 경우

삽입 정렬은 입력 자료가 정렬되어 있는 경우 가장 빠르다.

• $n-1$번의 외부 루프
• 각 단계에서 1번의 비교와 2번의 이동
  • 1번의 비교: 이미 정렬된 상태이므로 $k-1$번째 데이터는 무조건 $k$번째 데이터보다 작거나 같기 때문
  • 2번의 이동
    • key를 변수에 저장하는 데 1번
    • key를 원래 자리에 넣는 데 1번
    • 주의할 점
      • 이는 key 저장 또한 ‘이동’에 포함되는 것으로 봤기 때문. 관점에 따라서는 이 경우 이동은 없는 것으로도 볼 수 있다.²³
      • 중요한 것은 세세한 이동 횟수가 아닌, **최선의 경우의 삽입 정렬의 시간 복잡도는 $O(n)$**이라는 사실이다.⁴
  • 총 $n-1$번의 비교 횟수
    • $n$개의 데이터 중에서 첫 번째 데이터는 이미 정렬된 것으로 간주하므로.
  • 총 $2(n-1)$번의 이동 횟수

따라서 최선의 경우의 시간 복잡도는 $O(n)$

최악의 경우

반면 최악의 경우는 입력 자료가 역순일 경우이다. [6, 5, 4, 3, 2, 1]을 삽입 정렬 알고리즘으로 오름차순 정렬하는 경우를 예로 들 수 있다.

• $n-1$번의 외부 루프
• 입력 자료가 역순이므로, 정렬된 데이터 모두와 비교해야 한다.
  • 따라서 총 비교 횟수 = ${\sum }_{i=0}^{n-1}i=0+1+2+3+\cdots +(n-1)=\frac{n(n-1)}{2}=O(n^2)$
• 또한 각 단계에서 정렬된 데이터들을 모두 한 칸씩 뒤로 이동시켜야 하므로 각 단계마다 $i+2$의 이동이 발생한다.
  • $i+2$번의 이동
    • 이미 정렬된 데이터들을 뒤로 이동 = $i$번
    • key를 변수에 저장하는 데에 1번
    • 빈 공간에 key 삽입 = 1번
  • 따라서 총 이동 횟수 = $\frac{n(n-1)}{2}+{\sum }_{i=0}^{n-1}(i+2)=\frac{n(n-1)}{2}+2(n-1)=\frac{n^2+3n+4}{2}=O(n^2)$

따라서 최악의 경우의 삽입 정렬의 시간 복잡도는 $O(n^2)$이다.

평균적인 경우

마지막으로 평균적인 경우를 살펴보자면 데이터가 무작위로 섞여있는 경우다.

• 최선의 경우: 이미 정렬되었으므로 1번만 비교하고 바로 삽입.
• 최악의 경우: $i-1$개의 데이터와 비교.
• 평균적인 경우: 최악과 최선의 그 사이. 평균적으로 삽입 위치는 $\frac{i-1}{2}$
  • 총 비교 횟수 = ${\sum }_{i=0}^{n-1}\frac{i}{2}=\frac{1}{2}{\sum }_{i=0}^{n-1}i=\frac{1}{2}\cdot \frac{n(n-1)}{2}=O(n^2)$
  • 총 이동 횟수 = ${\sum }_{i=0}^{n-1}\frac{i+3}{2}=O(n^2)$
    • 정렬된 데이터들을 뒤로 이동 = $\frac{i-1}{2}$번
    • key를 변수에 저장 + 빈 공간에 key 삽입 = 2번

따라서 평균적인 경우의 삽입 정렬의 시간 복잡도는 $O(n^2)$이다.

특징

• 제자리 정렬이다.
• 안정성을 만족한다.
• 알고리즘이 간단하기 때문에 크기가 작은 배열에서 효과적이다.
• 부분적으로 정렬되었거나 이미 정렬된 상태일 때 매우 효율적이다.

구현

public class InsertionSort {
	public static void sort(int[] array) {
		int n = array.length;
		int i, j, key;
		
		for (i = 1; i < n; i++) {
			key = array[i];
			for (j = i - 1; j >= 0; j--) {
				if(array[j] > key) {
					array[j+1] = array[j];
				}
			}
			array[j+1] = key;
		}
	}
}

참고문헌

• 천인국, 공용해, 하상호, 『C언어로 쉽게 풀어쓴 자료구조』(개정 3판), 생능출판(2020)
• 기계인간 John Grib, 삽입 정렬(Insertion Sort), 2020.09.20, https://johngrib.github.io/wiki/insertion-sort/

Footnotes

1. 나무위키, 정렬 알고리즘, 2024.04.09 04:43:11, https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98?from=%EC%82%BD%EC%9E%85%20%EC%A0%95%EB%A0%AC#s-4.1.3 ↩

2. 로버트 세지윅, 케빈 웨인『알고리즘』(개정 4판), 권오인, 길벗(2018), p.249 ↩

3. 기계인간 John Grib, 삽입 정렬(Insertion Sort) 문서 참조 ↩

4. 이는 ‘최악의 경우’와 ‘평균적인 경우’에서도 마찬가지 ↩