버블 정렬(Bubble Sort)

버블 정렬은 알고리즘을 처음 공부할 때 가장 먼저 접하는 정렬 방식이다. 두 인접한 요소를 비교하고, 순서가 잘못되어 있으면 서로 교환하는 방식으로 작동한다. 이 과정을 반복하면 가장 큰 값이 배열의 오른쪽 끝으로 이동하게 되는데, 거품이 수면 위로 떠오르는 모습과 닮았다고 해서 ‘버블 정렬’이라는 이름이 붙었다. 버블 정렬의 핵심은 배열을 한 번 끝까지 훑을 때마다 오른쪽 끝에 ‘정렬된 값 하나’가 확정된다는 점이다. 요소가 n개라면 전체를 정렬하기 위해 필요한 반복 횟수는 n-1번이다. 마지막 하나는 자동으로 제자리를 찾기 때문이다.

작동 방식은 단순하다. 처음 훑을 때는 전체 요소를 앞에서부터 비교하여 가장 큰 값을 오른쪽 끝으로 보낸다. 다음 반복에서는 이미 오른쪽 끝이 정렬되어 있으니 그 전까지만 비교하면 된다. 이런 식으로 비교해야 하는 구간이 점점 줄어들며 정렬이 진행된다. 버블 정렬이 기본적이지만 비효율적이라고 평가되는 이유가 바로 여기에 있다. 비교와 교환을 계속 반복하기 때문에 배열이 길어질수록 작업량이 빠르게 증가한다.

시간 복잡도를 보면 더 명확하다. 전체를 훑는 과정이 최대 n-1번 반복되고, 각 반복 안에서는 남은 요소들끼리 다시 비교한다. 첫 번째에서는 n-1번, 두 번째에서는 n-2번… 이런 식으로 줄어들기 때문에 전체 비교 횟수는 (n-1) + (n-2) + … + 1이 된다. 등차수열의 합을 적용하면 총 비교 횟수는 n(n-1)/2가 되고, 이는 결국 O(n²)의 시간 복잡도를 의미한다. 입력값이 두 배로 늘어나면 비교 횟수는 네 배로 뛰는 셈이다. 이런 이유로 버블 정렬은 실제 서비스나 대규모 데이터 처리 환경에서는 거의 사용되지 않는다.

그렇다고 해서 버블 정렬이 쓸모없는 알고리즘은 아니다. 알고리즘의 기본 원리를 이해하기에 좋은 구조를 갖고 있고, ‘두 값을 비교하고 교환한다’는 직관적인 작동 방식 덕분에 구현이 매우 쉽다. 또한 안정 정렬이기 때문에 동일한 값을 가진 요소들의 상대적 순서를 유지한다. 교육적 목적이나 작은 규모의 데이터에서는 여전히 충분히 활용 가치가 있다.

버블 정렬을 이해할 때 중요한 포인트는 두 가지다. 첫째, 한 번 쭉 훑을 때마다 가장 큰 값이 오른쪽으로 이동하며 정렬해야 하는 구간이 계속 줄어든다는 점. 둘째, 이러한 구조 때문에 시간 복잡도가 O(n²)로 입력값 증가에 매우 취약하다는 점이다. 이 흐름만 잡고 있으면 버블 정렬의 작동 원리와 한계가 자연스럽게 보인다.