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

소가 아니라 4개의 요소에 대해서 비교, 교환을 수행하면 됩니다. 그러면 그림 6-9처럼 4개

의 요소에 대해서만 비교, 교환을 수행하겠습니다.

０ １ ２ ３ ４ ５ ６
1 3 4 9 6 7 8
비교하고 교환합니다.
1 3 4 9 6 7 8

1 3 4 9 6 7 8
비교는 하지만
교환하지는 않습니다.
1 3 4 6 9 7 8
[그림 6-9] 버블 정렬의 두 번째 패스

실습 6-3은 앞의 내용을 바탕으로 하여 개선한 함수입니다. bubble3.c도 실습 6-1의 swap 함수
와 main 함수가 필요합니다.

실습 6-3 •완성 파일 chap06/bubble3.c
01 /*--- 버블 정렬(버전 3 : 스캔 범위를 제한합니다.) ---*/
02 void bubble(int a[], int n)
03 {
04 int k = 0; /* a[k]보다 앞쪽의 요소는 정렬을 마친 상태입니다. */
05 while(k < n - 1) {
06 int j;
07 int last = n – 1; /* 마지막으로 교환을 수행한 위치를 저장합니다. */
08 for(j = n - 1; j > k; j--)
09 if(a[j - 1] > a[j]) {
10 swap(int, a[j – 1], a[j]); 패스
11 last = j;
12 }
13 k = last;
14 }
15 }

last는 각 패스에서 마지막으로 교환한 두 요소 가운데 오른쪽 요소(a[j])의 인덱스를 저장하기

위한 변수입니다. 교환을 수행할 때마다 오른쪽 요소의 인덱스 값을 last에 저장합니다. 하나
의 패스를 마쳤을 때 last 값을 k에 대입하여 다음에 수행할 패스의 범위를 제한합니다. 그러
면 다음 패스에서 마지막으로 비교할 두 요소는 a[k]와 a[k + 1]가 됩니다. 이때 bubble 함수
의 시작 부분에서 k 값을 0으로 초기화하는 이유는 첫 번째 패스에서는 모든 요소를 검사해야

하기 때문입니다.
그림 6-8에서 첫 번째 패스를 마칠 때의 last 값은 3입니다. 따라서 다음에 수행하는 두 번째 패스(그림 6-9)에서 j의 scan
은 6, 5, 4로 1씩 감소하면서 요소의 교환이 3회 이루어집니다.
06•정렬 207