버블 정렬: 인접 교환으로 이해하는 안정 정렬

인접 비교가 정렬 구간을 만드는 방식

버블 정렬은 이웃한 두 원소의 순서를 확인하고, 잘못된 경우에만 자리를 바꾼다. 한 번의 패스가 끝나면 해당 범위의 최댓값 또는 최솟값이 배열의 끝으로 이동한다. 이 과정을 반복하면서 정렬이 끝난 영역을 넓혀 간다.

비교 기반의 제자리 정렬이며, 같은 키를 가진 원소의 상대 순서를 보존하는 안정 정렬이다. 평균과 최악 시간 복잡도는 O(n^2)이고, 조기 종료를 적용한 거의 정렬된 입력에서는 최선 O(n)이다. 추가 공간은 O(1)만 사용한다.

교환 여부로 불필요한 패스를 줄인다

패스가 끝날 때마다 가장 큰 값이 배열 뒤쪽에 고정되므로, 다음 패스에서는 그 위치를 비교할 필요가 없다. 비교 상한을 줄이는 이유다.

패스 중 교환이 한 번도 일어나지 않았다면 입력은 이미 정렬된 상태다. 이때 반복을 즉시 멈추는 조기 종료를 적용할 수 있다. 반대로 역순 데이터에서는 비용이 가장 커지며, 평균·최악 O(n^2) 특성 때문에 대용량이나 무작위 입력에는 비효율적이다.

동일 키의 순서가 보존되어야 하는 보조 정렬 단계에서는 안정성이 장점이 된다. 다만 거의 정렬된 입력에서는 삽입 정렬도 유사한 효율성을 보인다.

비교 범위와 종료 조건

입력은 비교 가능한 원소 리스트 A와 선택적 비교자 cmp(a, b)다. 길이가 0 또는 1인 입력은 바로 반환한다. 이질적인 타입을 비교해야 한다면 사용자 정의 비교자가 필요하며, 비교자는 비결정적이거나 비추이적이어서는 안 된다.

각 반복에서 swapped를 false로 초기화한 뒤 0..n-2 범위의 인접 원소를 비교한다. 교환이 발생하면 플래그를 true로 바꾸고, 패스가 끝난 뒤 교환이 없었다면 종료한다. 그렇지 않으면 n=n-1로 비교 경계를 좁혀 다음 패스를 진행한다.

⤢✕

Python과 JavaScript 구현

두 구현 모두 입력 배열 자체를 정렬하고 반환한다. 비교 가능한 동형 타입을 사용하거나 비교자를 제공하는 것을 전제로 하며, 실행 환경은 Python 3.10+와 Node.js 18+다.

Python

# Python 3.10+
from typing import List, Callable, TypeVar

T = TypeVar("T")

def bubble_sort(a: List[T], cmp: Callable[[T, T], int] | None = None) -> List[T]:
    """
    버블 정렬: 제자리, 안정 정렬.
    cmp(a,b) > 0 이면 a가 b보다 크다고 판단.
    """
    if len(a) <= 1:
        return a
    def _gt(x: T, y: T) -> bool:
        return (cmp(x, y) if cmp else (x > y)) > 0 if cmp else x > y

    n = len(a)
    while True:
        swapped = False
        for j in range(0, n - 1):
            if _gt(a[j], a[j + 1]):
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
        n -= 1
    return a

if __name__ == "__main__":
    data = [5, 1, 4, 2, 8]
    print(bubble_sort(data))  # [1, 2, 4, 5, 8]

JavaScript (Node.js)

// Node.js 18+
function bubbleSort(arr, cmp) {
  if (!Array.isArray(arr) || arr.length <= 1) return arr;
  const greater = (a, b) => (cmp ? cmp(a, b) : a > b ? 1 : a < b ? -1 : 0) > 0;

  let n = arr.length;
  while (true) {
    let swapped = false;
    for (let j = 0; j < n - 1; j++) {
      if (greater(arr[j], arr[j + 1])) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break;
    n -= 1;
  }
  return arr;
}

// 예시
console.log(bubbleSort([5, 1, 4, 2, 8])); // [1, 2, 4, 5, 8]

선택하기 좋은 상황과 피해야 할 상황

버블 정렬은 비교와 교환의 정렬 메커니즘을 설명하거나, 다른 정렬의 성능 기준점으로 삼는 교육·디버깅 레퍼런스에 맞는다. 최근에 대부분 정렬된 버퍼처럼 레코드 수가 수십~수백 수준인 소형 데이터 처리에서도 조기 종료를 활용할 수 있다.

추가 메모리 0에 가까운 제자리 정렬이 필요하고 코드 풋프린트를 작게 유지해야 하는 임베디드·펌웨어 환경에서는 임시 선택지가 될 수 있다. 상위 키 기준으로 정렬된 결과를 유지하면서 보조 키를 미세 정렬하는 단계에도 안정 정렬 특성을 활용할 수 있다.

반면 범용 서비스 경로나 대용량 데이터에는 삽입 정렬, 퀵 정렬, 병합 정렬 같은 대안을 우선 검토하는 편이 낫다.

알고리즘	성능(평균/최악)	확장성(대용량 적합)	일관성(성능 변동)	안정성(Stable)	운영 편의(구현/메모리)
버블 정렬	O(n^2) / O(n^2), 최선 O(n)	낮음	비교적 일관(항상 느림)	예	매우 쉬움 / O(1)
삽입 정렬	O(n^2) / O(n^2), 최선 O(n)	낮음	입력 분포에 민감	예	쉬움 / O(1)
선택 정렬	O(n^2) / O(n^2)	낮음	일관	아니오	쉬움 / O(1)
퀵 정렬	O(n log n) / O(n^2)	높음	분포·피벗에 민감	아니오(일반)	보통 / O(log n)
병합 정렬	O(n log n) / O(n log n)	높음	일관	예	어려움 / O(n) 추가 메모리