거품 정렬은 알고리즘과 구현이 어렵지 않습니다. 알고리즘을 알고 나면 이름이 왜 거품 정렬인지 알게 됩니다.

거품 정렬은 맨 처음에 위치한 데이터와 바로 뒤에 있는 데이터부터 순서대로 두 데이터씩 비교합니다. 앞에 위치한 데이터가 뒤에 위치한 데이터보다 크면 두 데이터를 교체합니다. 첫 번째 순회가 끝나면 맨 마지막 데이터가 가장 큰 데이터가 됩니다. 순회를 되풀이할 때마다 맨 뒤에서부터 차례대로 가장 큰 데이터 순서로 정렬됩니다. 그림으로 살펴보겠습니다.

그림 15-7 거품 정렬 알고리즘 ①