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

06-2 버블 정렬

버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복합니다.

버블 정렬

아래의 배열을 이용해 버블 정렬에 대해 알아보겠습니다.

6 4 3 7 1 9 8

먼저 끝에 있는 두 요소 9와 8부터 시작합니다. 이때 오름차순으로 배열을 정렬하고자 한다면

왼쪽의 값이 오른쪽의 값보다 작아야 합니다. 따라서 9와 8을 교환하면 배열은 아래와 같은
상태가 됩니다.

6 4 3 7 1 8 9

그런 다음 뒤쪽에서 2, 3번째 요소(1, 8)를 비교합니다. 1은 8보다 작으므로 교환할 필요가 없습
니다. 이렇게 이웃한 요소를 비교하고 교환하는 작업을 첫 번째 요소까지 계속하면 그림 6-3과

같은 상태가 됩니다. 요소의 개수가 n개인 배열에서 n – 1회 비교, 교환을 하고 나면 가장 작은 요
소가 맨 처음으로 이동합니다. 그리고 이런 일련의 과정(비교, 교환 작업)을 패스(pass)라고 합니다.

０ １ ２ ３ ４ ５ ６
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 (n - 1) 회

6 4 1 3 7 8 9

가장 작은 요소가 맨
처음으로 이동합니다. 6 1 4 3 7 8 9

1 6 4 3 7 8 9
정렬이 끝난 상태
[그림 6-3] 버블 정렬의 첫 번째 패스

200 C 알고리즘