삽입 정렬 분석하기
ko.khanacademy.org
삽입 정렬의 분석
선택 정렬과 삽입 정렬은 배열의 인덱스를 통해 반복합니다. 삽입 정렬의 경우 1, 2, 3, ... , n-1의 요소에서 insert()를 호출합니다. 이는 선택 정렬의 함수였던 IndexOfMinimum()처럼 하위 배열의 크기에 따라 수행 시간이 달라지는 것과 비슷합니다. 즉, insert를 수행하는데 있어서 선택정렬만큼 시간이 걸린다는 의미입니다. 하지만, 경우에 따라서 훨씬 빠르게 정렬 되는 경우도 있습니다.
insert()를 호출하고 하위 배열에 삽입되는 값이 하위 배열의 모든 요소보다 작을 때를 가정해봅니다. 예를 들어 [2,3,5,7,11] 이라는 배열에서 0을 삽입하게 될 경우, 하위 배열의 모든 요소가 오른쪽으로 하나씩 움직여야합니다. 즉, k개의 요소가 있는 하위 배열에 삽입할 때 모든 k개가 오른쪽으로 한 칸씩 움직여야 할 수도 있습니다.
키 값과 배열의 요소 값을 검사하고 그 요소를 끼어넣기 위해 몇 줄의 코드가 필요한지 세기보다는 그냥 일정한 수의 코드 줄이 필요하다치고 상수값 c라고 해봅시다. 그러면 k개의 요소가 있는 하위 배열에의 삽입에는 c*k줄이 필요합니다.
insert()를 호출 할 때마다 하위 배열 왼쪽의 모든 요소보다 작은 값이 value값으로 들어간다 칩시다. insert()를 처음 호출했을때는 k=1만큼 계산됩니다. 두 번째에는 k=2만큼, 세 번째에는 k=3입니다. 이렇게 k=n-1이 되는 끝까지 계산하면 아래의 식이 나옵니다
c⋅1+c⋅2+c⋅3+⋯c⋅(n−1)=c⋅(1+2+3+⋯+(n−1))
이렇게 되면 c*(1+2+3+...+n-1)까지의 등차급수가 딸려나오게 됩니다. 이를 등차급수의 공식을 이용해서 표시하면 아래의 식이 나옵니다. (등차급수의 합 공식에 값을 대입)
c⋅(n−1+1)((n−1)/2)
이를 풀어쓰면
cn^2/2−cn/2
라는 식이 나옵니다. 여기에서 빅 세타 표기법에 따라서 낮은 차수의 항을 버리고, 상수인 c값과 1/2를 버리면 삽입 정렬에서 소요되는 시간은 Θ(n^2)가 됩니다.
하지만 위 경우는 하위 배열의 모든 요소보다 insert되는 값이 작은 경우입니다. 그렇지 않은 경우, 하위 배열의 첫 검사에서 insert되는 값이 더 크다면 삽입정렬은 어떤 요소도 오른쪽으로 밀어낼 필요가 없게되며 insert호출 시 상수의 시간만 소요됩니다. 이렇게 모든 insert에 상수만큼의 시간이 소요된다면 삽입정렬에 소요되는 시간은 Θ(n)으로 표시할 수 있습니다.
삽입정렬: 최악의 경우
즉, 실행시간이 Θ(n^2) 만큼 걸리는 경우는 하위 배열이 모두 삽입될 값보다 크고, 삽입될 값을 왼쪽 끝까지 밀어버린 상태입니다. 이러한 경우는 역순으로 정렬된 배열에서 발생합니다.
삽입정렬: 최상의 경우
하지만 이미 정렬된 배열에서 삽입될 값이 자신의 왼쪽에 있는 요소보다 항상 크거나 같다면 Θ(n) 의 시간만 걸립니다.
삽입정렬: 평균적인 경우
그럼 평균적인 경우를 생각해보겠습니다. 평균적으로 삽입이 진행될 때 배열의 중간만큼까지만 왼쪽으로 이동한다고 하겠습니다. 앞서 설명드린 최악의 경우 Θ(n^2)의 절반만큼 걸린다는 의미인데 점근적 표기법에선 상수인 계수는 고려하지 않기 때문에 여전히 Θ(n^2) 입니다.
거의 정렬된 배열에 삽입 정렬이 이루어지는 경우
배열이 거의 정렬되어 있고 새로운 값을 삽입시키려고합니다. 이는 왼쪽 하위 배열의 특정 상수에 17만큼 떨어져있습니다. 이 경우 insert() 호출 시 최대 17개의 상수를 오른쪽으로 밀어낸다는 의미입니다. 하지만 상수만큼의 시간이 추가되는 것이기 때문에 실행 시간은 Θ(n) 만큼 걸립니다.