[C] 삽입 정렬 (Insert Sort) 정의 / 코드

 삽입 정렬 (Insert Sort) 는 정렬되어 있는 영역에 새로운 데이터의 정렬 위치를 찾아서 삽입하는 방식을 반복하여 전체 데이터 영역을 정렬하는 방법이다. 데이터가 많아질수록 많은 시간이 걸리지만, 거품 정렬과 비교하여 구현 난이도가 비슷하면서도 성능이 개선된다.

 위의 그림과 같은 단계를 통해서 정렬이 진행된다. 정렬을 하고자하는 데이터 영역에서 1개의 요소는 기본적으로 정렬이 되어 있다고 본다(Step 1). 다음 요소를 이미 정렬되어 있는 데이터 영역에서 위치를 찾아서 삽입한다(Step 2 ~ 5). 이 방식은 기본적으로 거품 정렬과 같은 비교 횟수(1 + 2 + ... + (n-3) + (n-2) + (n-1) = n * (n-1)/2 = n(n-1)/2)를 가지게 된다.

 하지만, 이미 정렬되어 있는 데이터 영역의 가장 큰 요소와 새로 비교하게 되는 요소를 비교하여, 삽입이 필요하지 않을 때에는 1번의 비교만으로 1번의 Step 을 넘어갈 수 있다. 이미 정렬이 되어 있는 경우(최선의 경우), n-1 의 비교 횟수를 가지게 된다. 최선의 경우와 최악의 경우의 비교 횟수 평균은 (n(n-1)/2 + (n-1))/2 = (n^2 + n - 2)/4 가 된다. 최선의 경우와 최악의 경우의 평균만을 확인해보았지만, 이미 정렬된 데이터 영역에서는 새로운 요소를 모두 비교할 필요없이 자신의 위치를 찾을 수 있으므로, 정렬의 효율이 개선된다.

 

 삽입 정렬을 다음과 같이 구현하였다.

 iTemp_Processing 은 새로 비교하게 되는 요소의 위치를 저장하며, iTemp_Compare 가 이미 정렬되어 있는 데이터 영역에서 증가하며 값을 비교한다. 정렬할 때에 사용하는 Swap 함수, 이 정렬 사용하는 예제는 이전 글(링크 : [C] 거품 정렬 (Bubble Sort) 정의 / 코드 / 개선)에서 확인할 수 있다.