Page 205 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

０ １ ２ ３ ４ ５ ６
1 3 4 6 7 8 9

비교는 하지만 1 3 4 6 7 8 9 (n – 4) 회
교환하지는 않습니다.
1 3 4 6 7 8 9
6은 4번째 위치로
이동합니다.
1 3 4 6 7 8 9

정렬이 끝난 상태

[그림 6-7] 버블 정렬의 네 번째 패스

이미 배열이 정렬을 마친 상태라면 그 이후의 패스는 요소 교환을 하지 않습니다. 그림에서
는 이 모습을 생략했지만 다섯 번째, 여섯 번째 패스에서도 요소 교환을 하지 않습니다.

즉, 어떤 패스에서 요소의 교환 횟수가 0이면 더 이상 정렬할 요소가 없다는 뜻이기 때문에 정
렬 작업을 멈추면 됩니다. 처음 주어진 배열이 아래와 같은 상태라고 가정하겠습니다.

1 3 4 6 7 8 9

첫 번째 패스에서 교환이 수행되지 않으므로 첫 번째 패스를 마친 다음에 정렬 작업을 멈춥니
다. 이런 방식(멈춤)을 도입하면 정렬을 마친 배열이나 정렬이 거의 다 된 상태의 배열에 대한

비교 연산이 많이 생략되어 짧은 시간에 정렬을 마칠 수 있습니다. 실습 6-2는 이런 ‘멈춤’으
로 개선한 버블 정렬 함수(버전 2)입니다. bubble2.c는 매크로 함수인 swap 함수와 main
함수가 필요합니다. 실습 6-1을 참고하세요.

실습 6-2 •완성 파일 chap06/bubble2.c
01 /*--- 버블 정렬(버전 2 : 교환 횟수에 따라 정렬 작업을 멈춥니다.) ---*/
02 void bubble(int a[], int n)
03 {
04 int i, j;
05 for(i = 0; i < n - 1; i++) {
06 int exchg = 0; /* 패스에서 시도한 교환 횟수 */
07 for(j = n - 1; j > i; j--)
08 if(a[j – 1] > a[j]) {
09 swap(int, a[j – 1], a[j]); 패스
10 exchg++;
11 }
12 if(exchg == 0) break; /* 교환이 수행되지 않았다면 정렬을 멈춥니다. */
13 }
14 }

06•정렬 205