[C언어] 삽입정렬 알고리즘(insertion sort)

void InsertionSort(char *ar)
{
	int i, j;
	char temp;
	int num = strlen(ar);

	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);
     printf("정렬된 문자열 : %s\n", str);
}

프로그램 실행화면

삽입 정렬은 배열의 앞쪽부터 순회하면서 정렬해 오는데 앞쪽의 정렬된 부분에서 대상 레코드의 위치를 찾아서 삽입하는 알고리즘이다.

자기보다 더 큰 값을 계속 뒤로 보내면서 빈 칸 하나를 만든 후 자신보다 작거나 같은 값을 만날 때 그 오른쪽 위치에 삽입한다.

위 프로그램은 "complete"라는 문자열을 삽입 정렬 알고리즘으로 정렬하여 "ceelmopt" 문자열을 만든다.i 루프로 배열 끝까지 순회하되 두 번째 요소부터 시작한다.

왜냐하면 앞쪽의 한 문자만 보면 이 부분 문자열은 이미 정렬되어 있다고 볼 수 있기 때문이다.

j 루프는 ar[i] 문자(temp)와 바로 왼쪽의 문자를 비교하여 왼쪽이 더 클 경우 이 값을 오른쪽으로 한 칸 이동시킨다.

자기보다 더 큰 값을 계속 이동시키다가 크지 않은 값을 만나면 이 값 다음 자리에 ar[i]를 삽입한다.

참조 사이트