앞에서부터 인접한 두 원소를 비교해서 순서가 어긋나면 자리를 바꾸는 것을 끝까지 반복한다. 한 바퀴 돌면 가장 큰 값이 맨 뒤로 밀려나 확정되고, 그 다음 바퀴는 하나 짧아진다. 큰 값이 거품처럼 뒤로 떠오른다고 해서 붙은 이름이다.
복잡도와 성질
바깥 반복이 n-1번 돌고 안쪽이 n-1, n-2, 그렇게 1번까지 도니 (n-1) × n/2, 곧 O(n²)이다. 최선은 O(n)까지 내려가고 평균과 최악은 O(n²)이다.
공간복잡도는 O(1)이다. 교환만 하고 추가 배열을 쓰지 않으니 제자리 정렬이다. 값이 같으면 자리를 바꾸지 않으므로 원래 순서가 유지되는 안정 정렬이기도 하다.
두 가지 최적화
최적화가 둘 있다. 한 바퀴 도는 동안 교환이 한 번도 없었다면 이미 정렬된 것이니, 불리언 변수 하나로 확인하고 바로 빠져나오면 된다. 최선이 O(n)이 되는 건 이 최적화가 있을 때뿐이다. 그리고 i번째 바퀴가 끝나면 뒤쪽 i개는 확정이므로, 안쪽 반복을 arr.length - i까지만 돌면 헛일을 줄인다.
삽입 정렬보다 느린 이유
같은 O(n²)인 삽입 정렬보다도 교환 횟수가 많아 느리다. 배우는 순서상 처음 나오지만 실제로 고를 일은 없다. 다만 인접한 것만 바꾼다는 성질 때문에 안정 정렬의 예로 자주 등장한다.