삽입정렬(Insertion Sort)

삽입정렬(Insertion Sort)는 이미 정렬되어 있는 i 개 짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개 짜리 배열을 만드는 과정을 반복한다. 선택정렬(Selection Sort)과 버블정렬(Bubble Sort)이 n개짜리 배열로부터 시작하여 그 크기를 하나씩 줄여나가는데 반하여, 삽입정렬은 1개짜리 배열로부터 시작하여 그 크기를 하나씩 늘려가는 정렬이다.

위의 예제를 살펴보면 배열 A[]에서 루프문을 통해 i가 두번째 원소 부터 배열의 끝 원소까지 루프문을 돌면서 A[i]번째의 원소를 자리에 알맞게 넣는다. i가 두번째 원소를 가리킬때 A[2]인 10의 자리는 A[1]인 29와 위치가 바껴야 하므로 자리가 교체된다. i가 세번째 원소를 가르킬때 A[3]인 14의 위치는 A[1]인 10 다음에 와야하므로 A[2]인 29와 자리가 교체된다. i가 네번째 원소를 가리킬때 A[4]인 37의 자리는 그대로이므로 아무런 작업을 하지 않는다. i가 마지막인 다섯번째 원소를 가리킬때 A[5]인 13의 자리는 A[1]인 10의 자리 뒤에 위치해야 한다. 그러므로 A[2], A[3], A[4]를 한칸씩 뒤로 미루고 A[2]자리에 13을 삽입시킨다.

삽입정렬(Insertion Sort)의 슈도코드를 살펴보면 다음과 같다.

삽입정렬(Insertion Sort)의 수행시간을 살펴보면

①의 for 루프는 n-1번 반복

②의 삽입은 최악의 경우 i-1회 비교

따라서 삽입정렬의 시간복잡도는 다음과 같다.

• Worst case : 1 + 2 + ... + (n-2) + (n-1) = O(n^2)
• Average case : 1/2(1 + 2 + ... + (n-2) + (n-1)) = O(n^2)

삽입정렬의 슈도코드를 좀더 풀어쓰면 다음과 같다.