삽입 정렬 분석하기

선택 정렬과 같이 삽입 정렬은 배열의 인덱스를 통해 반복을 합니다. 삽입 정렬은 인덱스 $1,2,3,\dots ,n-1$‍의 요소에서 insert를 호출합니다. 각 indexOfMinimum을 수행하는데 걸리는 시간이 정렬된 하위 배열의 크기에 따라 달라지는 것처럼 각 insert를 수행하는데 걸리는 시간도 동일합니다. 사실 앞 문장에서 "동일하다"라는 단어는 "동일할 수 있다"이어야 합니다. 그 이유를 살펴봅시다.

insert를 호출하고 하위 배열에 삽입되는 값이 하위 배열의 모든 요소보다 작을 때의 경우를 생각해봅시다. 예를 들어 하위 배열 [2, 3, 5, 7, 11]에 0을 삽입할 경우, 하위 배열의 모든 요소는 오른쪽으로 하나씩 움직여야 합니다. 그러므로 일반적으로 $k$‍개의 요소가 있는 하위 배열에 삽입할 때, 모든 $k$‍개의 요소가 한 칸씩 움직여야 할 수도 있습니다. 키 값과 요소 값을 검사하고 그 요소를 끼워넣기 위해 몇 줄의 코드가 필요한지 세기보다는 그냥 일정한 수의 코드 줄이 필요하다고 하고 이를 상수값 $c$‍라고 합시다. 그러면 $k$‍개의 요소가 있는 하위 배열로의 삽입에는 $c\cdot k$‍줄이 필요합니다.

insert를 호출할 때마다 하위 배열 왼쪽의 모든 요소보다 작다고 합시다. insert를 처음 호출하면 $k=1$‍입니다. 두 번째로 호출하면 $k=2$‍입니다. 세 번째로 호출하면 $k=3$‍입니다. 이렇게 $k=n-1$‍이 되는 끝까지 합니다. 그러면 정렬도니 하위 배열에 삽입하는데 소요되는 시간은 다음과 같습니다.

$c\cdot 1+c\cdot 2+c\cdot 3+\cdots c\cdot (n-1)=c\cdot (1+2+3+\cdots +(n-1))$‍ .

이 합은 $n$‍까지가 아닌 $n-1$‍까지의 합이지만 등차급수입니다. 등차급수의 공식을 이용하면 정렬된 하위 배열에 삽입하는데 소요되는 시간은 다음과 같습니다.

$c\cdot (n-1+1)((n-1)/2)=c{n}^2/2-cn/2$‍ .

big-Θ 표기법을 이용하여, 낮은 차수 항 $cn/2$‍과 상수 $c$‍와 1/2을 버립니다. 따라서 삽입 정렬에 소요되는 시간은 $\mathrm{\Theta }(n^2)$‍입니다.

삽입 정렬이 $\mathrm{\Theta }(n^2)$‍보다 짧은 시간에 실행될 수 있을까요? 그렇습니다. 배열 [2, 3, 5, 7, 11] 이 있다고 합시다. 여기서 정렬된 하위 배열은 첫 네 개 항목이고 이제 11이라는 값을 삽입하는 것입니다 첫 번째 검사에서 11이 7보다 크기 때문에 하위 배열 내의 어떤 요소도 오른쪽으로 밀어낼 필요가 없다는 것을 알 수 있습니다. 이 경우 insert의 호출에는 상수의 시간만이 소요됩니다. 모든 insert의 호출에 상수의 시간이 걸린다고 합시다. $n-1$‍번 insert가 호출되고 각 호출 시마다 상수값 $c$‍만큼의 시간이 걸린다고 하면 삽입 정렬에 소요되는 총 시간은 $c\cdot (n-1)$‍이며, 이는 $\mathrm{\Theta }(n^2)$‍가 아닌 $\mathrm{\Theta }(n)$‍입니다.

이런 경우들이 일어날 수 있을까요? insert에 대한 호출이 모두 하위 배열 내 모든 요소를 오른쪽으로 하나씩 밀어내는 경우가 있을 수 있을까요? insert를 호출할 때 밀어내기가 한 번도 일어나지 않을 수 있을까요? 모두 가능합니다. 삽입될 키가 왼쪽에 있는 모든 항목보다 작을 경우 insert를 호출하면 모든 요소가 옆으로 밀려납니다. 그러므로 모든 요소가 자신의 왼쪽에 있는 모든 요소보다 작을 경우, 삽입 정렬의 실행 시간은 $\mathrm{\Theta }(n^2)$‍입니다. 모든 요소가 자신의 왼쪽에 있는 요소보다 작다는 것은 무슨 뜻일까요? 시작할 때 배열이 [11, 7, 5, 3, 2] 와 같이 역순으로 정렬되어 있다는 뜻입니다. 그러므로 역순으로 정렬된 배열에서 삽입 정렬은 가장 오랜 시간이 걸립니다.

반대의 경우는 어떨까요? 삽입될 키가 왼쪽의 모든 요소보다 크거나 같을 경우 insert의 호출에서는 어떤 요소도 밀려나지 않습니다. 그러므로 만일 모든 요소가 자신의 왼쪽에 있는 요소보다 크거나 같을 경우, 삽입 정렬의 실행 시간은 $\mathrm{\Theta }(n)$‍이 됩니다. 이 경우는 시작할 때 배열이 이미 정렬되어 있을 때 일어납니다. 그러므로 이미 정렬된 배열에서 삽입 정렬은 가장 짧은 시간이 소요됩니다.

삽입 정렬의 실행 시간에 대해 언급할 사항이 또 무엇이 있을까요? 임의의 순서로 되어 있는 배열로 시작한다고 합시다. 그러면 평균적으로 각 요소는 자신의 왼쪽에 있는 요소의 절반보다는 작을 것입니다. 그러면 $k$‍개의 요소가 있는 하위 배열에서 insert를 호출하면 평균적으로 그 중 $k/2$‍개를 밀어낼 것입니다. 실행 시간은 최악의 경우의 실행 시간의 절반이 될 것입니다. 그렇지만 상수인 계수는 고려하지 않는 점근적 표기법에서 평균 실행 시간은 여전히 최악의 경우과 마찬가지로 $\mathrm{\Theta }(n^2)$‍입니다.

배열이 "거의 정렬되어" 있다는 것을 알고 있다면 어떨까요? 모든 요소가 정렬되었을 때의 위치에서 어떤 상수의 위치만큼 떨어져 있다면 어떨까요? 이 상수가 17인 경우를 봅시다. 이 경우 insert 호출은 최대 17개의 요소를 밀어낼 것이고 $k$‍개의 요소가 있는 하위 배열에 대한 insert의 호출 한 번에 걸리는 시간은 최대 $17\cdot c$‍가 될 것입니다. insert를 $n-1$‍번 호출하는 실행 시간은 $17\cdot c\cdot (n-1)$‍ 즉, 최상의 경우와 같이 $\mathrm{\Theta }(n)$‍입니다. 그러므로 삽입 정렬은 거의 정렬된 배열에서 빠르게 실행됩니다.

삽입 정렬의 실행 시간을 정리하면 다음과 같습니다.

삽입 정렬의 모든 경우에 대해 포괄적으로 표현해야 한다면, 삽입 정렬은 $O(n^2)$‍동안 실행된다고 해야 할 것입니다. 최상의 경우에서는 $\mathrm{\Theta }(n)$‍ 시간 내에 실행되기 때문에 모든 경우에서 $\mathrm{\Theta }(n^2)$‍ 시간 내에 실행된다고 할 수는 없습니다. 마찬가지로 최악의 경우 실행 시간이 $\mathrm{\Theta }(n^2)$‍이기 때문에 모든 경우에서 $\mathrm{\Theta }(n)$‍ 시간 내에 실행된다고도 할 수 없습니다.

위 자료는 다트머스 대학교 컴퓨터공학과의 토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.