이제 7은 확실히 배열 내에서 올바른 위치에 있다. 적절한 위치에 도달할 때까지 7을 계속해서 오른쪽으로 옮겼기 때문이다. 그림 4-11에서는 7 주변을 점선으로 표시해서 7이 올바른 위치에 있음을 나타냈다.

이 알고리즘을 버블 정렬이라 부르는 까닭이 바로 여기에 있다. 각 패스스루마다 정렬되지 않은 값 중 가장 큰 값, “버블”이 올바른 위치로 가게 된다.

첫 번째 패스스루에서 교환을 적어도 한 번 수행했으니 다음 패스스루도 수행해야 한다.

두 번째 패스스루를 시작하자.

8단계: 2와 4를 비교한다.

▲ 그림 4-12

올바른 순서이므로 다음 단계로 넘어간다.

9단계: 4와 1을 비교한다.

▲ 그림 4-13