선택 정렬과 같이 삽입 정렬은 배열의 인덱스를 통해 반복을 합니다. 삽입 정렬은 인덱스 1,2,3,,n1 1, 2, 3, \ldots, n-1 의 요소에서 insert를 호출합니다. 각 indexOfMinimum을 수행하는데 걸리는 시간이 정렬된 하위 배열의 크기에 따라 달라지는 것처럼 각 insert를 수행하는데 걸리는 시간도 동일합니다. 사실 앞 문장에서 "동일하다"라는 단어는 "동일할 수 있다"이어야 합니다. 그 이유를 살펴봅시다.
insert를 호출하고 하위 배열에 삽입되는 값이 하위 배열의 모든 요소보다 작을 때의 경우를 생각해봅시다. 예를 들어 하위 배열 [2, 3, 5, 7, 11]에 0을 삽입할 경우, 하위 배열의 모든 요소는 오른쪽으로 하나씩 움직여야 합니다. 그러므로 일반적으로 k개의 요소가 있는 하위 배열에 삽입할 때, 모든 k개의 요소가 한 칸씩 움직여야 할 수도 있습니다. 키 값과 요소 값을 검사하고 그 요소를 끼워넣기 위해 몇 줄의 코드가 필요한지 세기보다는 그냥 일정한 수의 코드 줄이 필요하다고 하고 이를 상수값 c라고 합시다. 그러면 k개의 요소가 있는 하위 배열로의 삽입에는 c, dot, k줄이 필요합니다.
Suppose that upon every call to insert, the value being inserted is less than every element in the subarray to its left. When we call insert the first time, k, equals, 1. The second time, k, equals, 2. The third time, k, equals, 3. And so on, up through the last time, when k, equals, n, minus, 1. Therefore, the total time spent inserting into sorted subarrays is
c1+c2+c3+c(n1)=c(1+2+3++(n1)) c \cdot 1 + c \cdot 2 + c \cdot 3 + \cdots c \cdot (n-1) = c \cdot (1 + 2 + 3 + \cdots + (n-1)) .
That sum is an arithmetic series, except that it goes up to n, minus, 1 rather than n. Using our formula for arithmetic series, we get that the total time spent inserting into sorted subarrays is
c, dot, left parenthesis, n, minus, 1, plus, 1, right parenthesis, left parenthesis, left parenthesis, n, minus, 1, right parenthesis, slash, 2, right parenthesis, equals, c, n, start superscript, 2, end superscript, slash, 2, minus, c, n, slash, 2 .
Using big-Θ notation, we discard the low-order term c, n, slash, 2 and the constant factors c and 1/2, getting the result that the running time of insertion sort, in this case, is Θ(n2) \Theta(n^2) .
삽입 정렬이 Θ(n2) \Theta(n^2) 보다 짧은 시간에 실행될 수 있을까요? 그렇습니다. 배열 [2, 3, 5, 7, 11] 이 있다고 합시다. 여기서 정렬된 하위 배열은 첫 네 개 항목이고 이제 11이라는 값을 삽입하는 것입니다 첫 번째 검사에서 11이 7보다 크기 때문에 하위 배열 내의 어떤 요소도 오른쪽으로 밀어낼 필요가 없다는 것을 알 수 있습니다. 이 경우 insert의 호출에는 상수의 시간만이 소요됩니다. 모든 insert의 호출에 상수의 시간이 걸린다고 합시다. n, minus, 1insert가 호출되고 각 호출 시마다 상수값 c만큼의 시간이 걸린다고 하면 삽입 정렬에 소요되는 총 시간은 c, dot, left parenthesis, n, minus, 1, right parenthesis이며, 이는 Θ(n2) \Theta(n^2) 가 아닌 Θ(n) \Theta(n) 입니다.
이런 경우들이 일어날 수 있을까요? insert에 대한 호출이 모두 하위 배열 내 모든 요소를 오른쪽으로 하나씩 밀어내는 경우가 있을 수 있을까요? insert를 호출할 때 밀어내기가 한 번도 일어나지 않을 수 있을까요? 모두 가능합니다. 삽입될 키가 왼쪽에 있는 모든 항목보다 작을 경우 insert를 호출하면 모든 요소가 옆으로 밀려납니다. 그러므로 모든 요소가 자신의 왼쪽에 있는 모든 요소보다 작을 경우, 삽입 정렬의 실행 시간은 Θ(n2) \Theta(n^2) 입니다. 모든 요소가 자신의 왼쪽에 있는 요소보다 작다는 것은 무슨 뜻일까요? 시작할 때 배열이 [11, 7, 5, 3, 2] 와 같이 역순으로 정렬되어 있다는 뜻입니다. 그러므로 역순으로 정렬된 배열에서 삽입 정렬은 가장 오랜 시간이 걸립니다.
반대의 경우는 어떨까요? 삽입될 키가 왼쪽의 모든 요소보다 크거나 같을 경우 insert의 호출에서는 어떤 요소도 밀려나지 않습니다. 그러므로 만일 모든 요소가 자신의 왼쪽에 있는 요소보다 크거나 같을 경우, 삽입 정렬의 실행 시간은 Θ(n) \Theta(n) 이 됩니다. 이 경우는 시작할 때 배열이 이미 정렬되어 있을 때 일어납니다. 그러므로 이미 정렬된 배열에서 삽입 정렬은 가장 짧은 시간이 소요됩니다.
삽입 정렬의 실행 시간에 대해 언급할 사항이 또 무엇이 있을까요? 임의의 순서로 되어 있는 배열로 시작한다고 합시다. 그러면 평균적으로 각 요소는 자신의 왼쪽에 있는 요소의 절반보다는 작을 것입니다. 그러면 k개의 요소가 있는 하위 배열에서 insert를 호출하면 평균적으로 그 중 k, slash, 2개를 밀어낼 것입니다. 실행 시간은 최악의 경우의 실행 시간의 절반이 될 것입니다. 그렇지만 상수인 계수는 고려하지 않는 점근적 표기법에서 평균 실행 시간은 여전히 최악의 경우과 마찬가지로 Θ(n2) \Theta(n^2) 입니다.
배열이 "거의 정렬되어" 있다는 것을 알고 있다면 어떨까요? 모든 요소가 정렬되었을 때의 위치에서 어떤 상수의 위치만큼 떨어져 있다면 어떨까요? 이 상수가 17인 경우를 봅시다. 이 경우 insert 호출은 최대 17개의 요소를 밀어낼 것이고 k개의 요소가 있는 하위 배열에 대한 insert의 호출 한 번에 걸리는 시간은 최대 17, dot, c가 될 것입니다. insertn, minus, 1번 호출하는 실행 시간은 17, dot, c, dot, left parenthesis, n, minus, 1, right parenthesis 즉, 최상의 경우와 같이 Θ(n) \Theta(n) 입니다. 그러므로 삽입 정렬은 거의 정렬된 배열에서 빠르게 실행됩니다.
삽입 정렬의 실행 시간을 정리하면 다음과 같습니다.
  • 최악의 경우: Θ(n2) \Theta(n^2) .
  • 최상의 경우: Θ(n) \Theta(n) .
  • 임의의 배열에 대한 평균적 경우: Θ(n2) \Theta(n^2) .
  • "거의 정렬된" 경우: Θ(n) \Theta(n) .
삽입 정렬의 모든 경우에 대해 포괄적으로 표현해야 한다면, 삽입 정렬은 O, left parenthesis, n, start superscript, 2, end superscript, right parenthesis동안 실행된다고 해야 할 것입니다. 최상의 경우에서는 Θ(n) \Theta(n) 시간 내에 실행되기 때문에 모든 경우에서 Θ(n2) \Theta(n^2) 시간 내에 실행된다고 할 수는 없습니다. 마찬가지로 최악의 경우 실행 시간이 Θ(n2) \Theta(n^2) 이기 때문에 모든 경우에서 Θ(n) \Theta(n) 시간 내에 실행된다고도 할 수 없습니다.

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