버블 정렬에서 일어나는 비교 횟수를 분석했으니 이제 교환을 분석해 보자.

배열이 내림차순으로(우리가 원하는 것과 완전히 정반대로) 정렬된 최악의 시나리오라면 비교할 때마다 교환을 해야 한다. 즉, 이러한 시나리오에서는 비교 10번, 교환 10번이 일어나 총 20단계가 필요하다.

이제 전체적인 그림을 보자. 원소 5개가 역순으로 된 배열에서는 4 + 3 + 2 + 1 = 10번 비교해야 한다. 10번의 비교와 더불어 교환도 10번 해야 하니 총 20단계다.

값 10개가 역순으로 된 배열에서는 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45번의 비교와 45번의 교환이 일어난다. 총 90단계다.

원소가 20개인 배열에서는

19 + 18 + 17 + 16 + 15 + 14 + 13 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 190번의 비교와 약 190번의 교환이 일어나므로 총 380단계다.

얼마나 비효율적인가. 원소 수가 증가할수록 단계 수가 기하급수적으로 늘어난다. 다음의 표로 명확하게 알 수 있다.

▼ 표 4-1