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

Q1 버블 정렬의 각 패스에서 비교, 교환은 처음(왼쪽)부터 수행해도 됩니다(각 패스에서 가장
연습
문제 큰 값의 요소가 끝으로 옮겨집니다). 그렇게 수정한 프로그램을 작성하세요.

Q2 오른쪽처럼 비교, 교환 과정을 자세히 출력하면서 버블 패스1:
6 4 3 7 1 9 + 8
정렬하는 프로그램을 작성하세요. 비교하는 두 요소 사이에 교 6 4 3 7 1 - 8 9
환을 수행하면 '+', 수행하지 않으면 '–'를 출력하고 정렬을 마 6 4 3 7 + 1 8 9
6 4 3 + 1 7 - 8 9
치면 비교 횟수와 교환 횟수를 출력하세요. 6 4 + 1 3 7 8 9
6 + 1 4 3 7 8 9
1 6 4 3 7 8 9
패스2:
1 6 4 3 7 - 8 - 9
… 중략 …
비교를 21회 했습니다.
교환을 8회 했습니다.

알고리즘 개선(1)
그림 6-4에는 두 번째 요소까지 정렬된 모습을 나타냈습니다. 비교, 교환 작업을 계속하면서
이 알고리즘을 어떻게 개선할 수 있을지 살펴보겠습니다. 그림 6-6은 세 번째 패스입니다. 패

스를 마치고 나면 4가 3번째 자리에 위치합니다.

０ １ ２ ３ ４ ５ ６
1 3 6 4 7 8 9
비교하고 교환합니다.
1 3 6 4 7 8 9
(n – 3) 회
1 3 6 4 7 8 9
비교는 하지만
교환하지는 않습니다.
1 3 6 4 7 8 9
4는 3번째 위치로 이동합니다.
1 3 4 6 7 8 9

정렬이 끝난 상태
[그림 6-6] 버블 정렬의 세 번째 패스

그림 6-7은 네 번째 패스입니다. 그런데 여기서는 요소의 교환이 한 번도 이루어지지 않습니
다. 왜냐하면 세 번째 패스에서 정렬을 마쳤기 때문입니다.

204 C 알고리즘