버블 정렬 알고리즘은 두 가지 중요한 단계를 포함한다.

먼저 버블 정렬에서 얼마나 많은 비교가 일어나는지 알아내 보자.

예제의 배열은 원소가 5개다. 다시 살펴보면 첫 번째 패스스루에서 두 수의 비교를 4번 해야 했다.

두 번째 패스스루에서는 비교를 3번만 했다. 첫 번째 패스스루를 거치면서 마지막 숫자가 올바른 위치로 갔음을 이미 알고 있었으므로 마지막 두 수를 비교할 필요가 없었기 때문이다.

세 번째 패스스루에서는 비교를 2번 했고, 네 번째 패스스루에서는 비교를 딱 1번만 했다.

따라서,

4 + 3 + 2 + 1 = 10번의 비교다.

모든 배열 크기에 적용되도록 표현하면 원소 N개가 있을 때,

(N - 1) + (N - 2) + (N - 3) … + 1번의 비교를 수행한다.