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

변수 exchg는 패스를 시작하기 전에 0으로 초기화되고 패스에서 요소를 교환할 때마다 1씩

증가합니다. 따라서 패스를 마쳤을 때의 exchg 값은 한 번의 패스에서 시도한 교환 횟수와 같
습니다. 이때 exchg 값이 0이면 정렬을 마친 것이므로 break문으로 함수를 종료합니다.

연습 Q3 버블 정렬(버전 2)의 아이디어는 배열이 정렬을 마쳤는지를 검사하는 데 응용할 수 있습니
문제 다. 전달받은 배열 a가 오름차순으로 정렬을 마쳤는지 검사하는 함수를 작성하세요. 이때 오름차
순으로 정렬을 마친 상태라면 1, 그렇지 않으면 0을 반환하도록 작성하세요.

int is_sorted(const int a[], int n);

Q4 버블 정렬(버전 2)을 연습문제 Q2(204쪽)처럼 비교, 교환 과정을 자세히 출력하는 프로
그램으로 수정하세요.

알고리즘 개선(2)

다시 새로운 배열({1, 3, 9, 4, 7, 8, 6})에 대해서 버블 정렬을 수행하겠습니다. 그림 6-8은 첫 번
째 패스의 비교, 교환 과정을 나타낸 것입니다.

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

비교하고 교환합니다.
1 3 9 4 7 6 8

비교는 하지만 1 3 9 4 6 7 8
교환하지는 않습니다.
1 3 9 4 6 7 8 ★ 마지막 교환

1 3 4 9 6 7 8

1 3 4 9 6 7 8 교환 없음
마지막으로 교환을 한 위치 이후
最後に交換した位置より先의
頭側はソートずみ
요소는 정렬을 마친 상태입니다. 1 3 4 9 6 7 8

[그림 6-8] 버블 정렬의 첫 번째 패스

교환을 마치고 난 이후의 세 요소({1, 3, 4})는 정렬된 상태입니다. 이렇게 각각의 패스에서 비
교, 교환을 하다가 어떤 시점 이후에 교환이 수행되지 않는다면 그보다 앞쪽의 요소는 이미
정렬을 마친 상태라고 생각해도 좋습니다. 따라서 두 번째 패스는 첫 요소를 제외한 6개의 요

206 C 알고리즘