20-2-다.삽입 정렬

삽입 정렬은 배열의 앞쪽부터 순회하면서 정렬해 오는데 앞쪽의 정렬된 부분에서 대상 레코드의 위치를 찾아서 삽입하는 알고리즘이다. 자기보다 더 큰 값을 계속 뒤로 보내면서 빈 칸 하나를 만든 후 자신보다 작거나 같은 값을 만날 때 그 오른쪽 위치에 삽입한다. 다음 예제는 "complete"라는 문자열을 삽입 정렬 알고리즘으로 정렬하여 "ceelmopt" 문자열을 만든다.

예 제 : InsertionSort

#include <Turboc.h>

void InsertionSort(char *ar, int num)

{

int i,j;

char temp;

// 두 번째 요소부터 끝까지 순회

for (i=1;i<num;i++) {

// 앞쪽으로 이동하면서 자기보다 큰 값을 한칸씩 오른쪽으로 이동한다.

for (temp=ar[i],j=i;j>0;j--) {

if (ar[j-1] > temp) {

ar[j]=ar[j-1];

} else {

break;

}

}

// 자기보다 크지 않은 최초의 칸 자리에 자신을 삽입한다.

ar[j]=temp;

}

}

void main()

{

char str[]="complete";

printf("정렬 전의 문자열 : %s\n",str);

InsertionSort(str,strlen(str));

printf("정렬된 문자열 : %s\n",str);

}

i 루프로 배열 끝까지 순회하되 두 번째 요소부터 시작한다. 왜냐하면 앞쪽의 한 문자만 보면 이 부분 문자열은 이미 정렬되어 있다고 볼 수 있기 때문이다. j 루프는 ar[i] 문자(temp)와 바로 왼쪽의 문자를 비교하여 왼쪽이 더 클 경우 이 값을 오른쪽으로 한 칸 이동시킨다. 자기보다 더 큰 값을 계속 이동시키다가 크지 않은 값을 만나면 이 값 다음 자리에 ar[i]를 삽입한다. 예제의 동작 단계를 그림으로 연구해 보자.

최초 i가 1일 때, 즉 ar[i]가 o일 때 왼쪽 문자와 크기를 비교해 보니 바로 왼쪽의 c가 자신보다 더 작다. 그러므로 이때는 교환을 할 필요가 없으며 이 상태에서 co까지 부분 정렬을 완료한다. i가 2일 때 m과 오른쪽의 o를 비교해 보니 o가 더 뒤쪽으로 와야 한다. 그래서 o를 뒤로 이동시키고 다음 자리와 비교하는데 c가 m보다 크지는 않으므로 이 자리에 m이 삽입된다. 여기까지 cmo가 부분적으로 정렬되었다.

다음 단계의 p문자는 앞쪽의 부분 정렬된 cmo에 끼어들 자리가 없으므로 이 자리에 가만히 있으면 된다. 왜냐하면 부분 정렬된 문자열중 가장 큰 값 o가 자신보다 더 작기 때문이다. cmop까지 정렬이 완료되었다. i가 4일 때 l을 앞 쪽의 부분 정렬 결과인 cmop에서 l의 자리를 찾아 삽입하는데 이 과정은 좀 더 상세하게 단계별로 분석해 보자.

먼저 temp에 ar[i]의 값 l을 복사해 둔다. 그리고 j를 i부터 배열 앞쪽으로 이동시키면서 왼쪽 요소와 비교하는데 첫 번째 루프에서 p가 l보다 크므로 p를 오른쪽의 l자리로 이동시킨다. 다음 루프에서 l보다 더 큰 o가 p자리로 오고 m이 o자리로 온다. 다음 단계에서 c는 l보다 크지 않으므로 이때 j루프를 탈출하는데 m이 원래 있던 자리는 빈칸이 되어 있다. 이 빈칸에 temp에 저장된 l을 삽입하면 l이 제자리를 찾는다.

이런 식으로 앞쪽의 부분 문자열에서 자기보다 더 큰 값을 계속 뒤쪽으로 이동시키며 자신이 들어갈 자리를 찾아 삽입되는 것이다. 다음 i루프에서는 e가 제일 앞쪽으로 이동하고 t는 부분 정렬된 문자열 중에 제일 크므로 아무 일도 일어나지 않는다. 마지막으로 제일 끝에 있는 e가 두 번째 위치로 이동하는데 제일 처음의 e와는 같은 값이지만 같은 값을 만날 때 그 오른쪽 자리에 삽입한다. 그래서 삽입 정렬은 같은 값끼리 원래 순서가 유지되는 안정성이 있다.

삽입 정렬 속도를 개선하는 여러 가지 방법들이 연구되어 있는데 배열의 제일 첫 요소에 가장 작은 값을 미리 배치하거나 아니면 충분히 작은 더미값을 배치하여 j가 배열 범위를 벗어나지 않도록 하는 방법이 있다. 또 배열의 앞쪽은 항상 정열되어 있으므로 새로운 값이 삽입될 위치를 이분 검색으로 찾아 일괄적으로 배열 요소를 이동하는 방법이 사용되기도 한다.

쉘 정렬(Shell Sort)은 삽입 정렬을 개선한 좀 빠른 알고리즘이다. 삽입 정렬은 인접 요소끼리 비교하여 자리를 이동하는데 비해 쉘 정렬은 일정수만큼 건너뛰면서 비교하여 교환하는 알고리즘이다. 이때 몇 칸씩 건너뛸 것인가에 따라 구현이 조금씩 달라지는데 임의의 데이터에 대해서도 항상 제 속도가 나와 퀵 정렬만큼이나 빠르다.