삽입정렬(Insertion Sort)

 

문은영 교수님의 데이터구조 수업 자료입니다. 문제시 삭제하겠습니다.

방식

i가 0 ~ n-1 일 때, 왼쪽 카드가 지금 카드보다 크다면 교환한다. 그렇지 않다면 다음 iteration으로 넘어간다.

이 작업을 index i부터 1까지 매 iteration에서 반복한다.

일부 항목만 정렬이 흐트러졌을 때 사용하면 유리한데,

1. 배열이 이미 정렬되었을 경우 linear time으로 동작하고

2. 구현이 쉽기 때문이다.

 

시간복잡도

Avg - O(n^2)

iteration i에서 벌어지는 swap과 비교 횟수의 평균은 각각 i/2회이다.

시간복잡도를 big-O natation으로 표현하면 O(T(n)) = O(n(n-1)/4) = O(n^2) 이다.

 

Best - O(n)

배열이 이미 정렬되었을 때 각 iteration 마다 비교 한번만 수행하므로 O(n)이다.

 

Worst - O(n^2)

O(n^2)

각 iteration i에서 매번 swap을 해야하는 상황이 worst case이다.

iteration i에서는 swap i번, 비교 i번을 수행하게 된다.

따라서 O(T(n)) = O(n(n-1)/2) = O(n^2)이다.

 

증명

왜 left element가 right element보다 작으면 바로 swap을 멈출 수 있는가?

수학적 귀납법으로 설명할 수 있다.

조건으로 주어진 index i-1 원소가 index i 원소보다 작은 상황을 L(i)라고 하자.

index k 밑으로 오름차순 정렬되어있다는 것은 x < k 를 만족하는 x에 대해 항상 arr[x] < arr[x+1] 를 만족한다는 것과 동치이다. 앞으로 이 명제를 S(k)라고 하자.

i = 1일 때, arr[0] < arr[1] 이라면 (L(1)이 참이라면) x < 1을 만족하는 모든 x에 대해 arr[x] < arr[x+1] 을 만족하으로 index 1 밑으로 오름차순 정렬되어있다는 것이 보장된다. (S(1) is true)

그리고 i = k일 때, arr[k-1] < arr[k] 이고 (L(k)가 참), i = k-1 일 때 x < k-1을 만족하는 모든 x에 대해 arr[x] < arr[x+1] 임이 보장된다면 (S(k-1)가 참) x < k에 대해서도 S(k)가 참임이 보장된다.

정리하면 S(k-1) and L(k) → S(k) 가 성립하는 것이다.

이때 L(k)는 가정에 의해 항상 참이고, S(1)은 항상 참이므로 수학적 귀납법에 의해서 S(k)도 항상 참이다.

 

참고 자료

유튜브 강의 : https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4