▷ 이미 정렬되어 있는 곳에 새로운 레코드를 '삽입(Insertion)하는 방식이다. 정렬되어 있지 않은 랜덤값의 경우에는 맨 앞의 단 한 개의 레코드가 정렬되어있다고 가정하고 정렬을 시작하게 된다.
두 번째 값을 읽었을 때에는 이미 정렬되었다고 여긴 첫 번째 값과 비교하여 순위를 정하고 두 개만 가지고 자체적으로 정렬을 한다. 세 번째 값을 읽었을 때에는 이미 정렬된 앞의 두 값과 비교하여 세 번째 값의 크기에 적합한 위치로 정렬되어 들어가게 된다.데이터의 크기만큼 위와 같은 단계를 반복한다.
이미 정렬된 앞의 값들과 새로 들어올 값의 비교를 위해서, 하나의 값이 들어갈 때마다 가장 오른쪽의 최고로 큰 수부터 하나씩 크기비교를 하게 되며, 들어가려고 하는 값보다 더 작은 값이 나올 때까지 계속 왼쪽으로 가면서 크기비교를 해서 드디어 더 작은 값을 찾았을 때 그곳의 오른쪽에 새로 들어올 값이 삽입(Insertion)되는 방식이다.
따라서 만약 큰 배열에 Insertion Sort를 행할 때 큰 값의 경우에는 정렬이 빠르게 되지만 작은 값들이 많이 입력되면 뒤에서부터 계속 하나씩 비교해야만 하므로 효율이 떨어질 수 있다. 또한 하나의 값을 입력하였을 때 평균적으로 전체 배열의 반과 비교해야만 함을 알 수가 있다.
Insertion Sort의 이러한 특성을 알고 적절한 곳에 사용하면 좋을 것이다.
■ 삽입정렬의 동작 알고리즘
1. 정렬 할 레코드를 임시 변수에 저장한다
2. 정렬 할 레코드와 앞의 정렬된 레코드와 비교하여 정렬 할 레코드의 값이 더 작으면 정렬 된 레코드를
한칸 뒤로 옮기고 한칸 더 앞의 레코드와 비교한다.
3. 정렬할 레코드의 값이 더 크면 현재위치에 임시변수에 저장된 값을 넣는다.
------------------------------------------------------------------------------------------------
void insert_sort(int *data_temp, int n)
{
int i, j, temp;
for ( i = 1; i < n; i++ )
{
temp = data_temp[i];
j = i;
// 삽입될곳을 찾기
while ( (data_temp[j-1] > temp) && (j > 0) )
{
// 뒤로옮긴후
data_temp[j] = data_temp[j-1];
j--;
}
// 삽입한다
data_temp[j] = temp;
}
}
------------------------------------------------------------------------------------------------
출처 : http://blog.naver.com/iouun
