버블 정렬: 이웃 비교로 가장 큰 값을 뒤에 확정하기

버블 정렬은 이웃한 두 값의 순서가 틀리면 바꿉니다. 왼쪽에서 오른쪽으로 한 번 지나가면 아직 정렬하지 않은 구간의 최댓값이 맨 뒤에 도착합니다.

선수 지식: 배열 인덱스, 이중 반복문, 두 변수의 값 교환

• 한 번의 패스가 보장하는 결과를 설명합니다.
• 정렬이 확정된 뒤쪽 구간을 비교에서 제외합니다.
• 조기 종료가 최선 시간에 주는 영향을 구분합니다.

전체를 보지 않고 이웃의 순서부터 맞춥니다

[4, 2, 3, 1]에서 처음 이웃한 4와 2를 비교합니다. 오름차순에서는 왼쪽 값이 더 작거나 같아야 하므로 둘을 바꿔 [2, 4, 3, 1]로 만듭니다. 다음에는 방금 오른쪽으로 이동한 4와 3을 비교합니다. 다시 바꾸면 4가 한 칸 더 이동합니다. 이처럼 큰 값이 이웃 비교를 따라 오른쪽으로 밀립니다.

한 번 비교했다고 왼쪽 원소의 최종 위치가 정해지는 것은 아닙니다. 첫 교환 뒤 인덱스 0에 온 2보다 작은 1이 아직 뒤에 남아 있습니다. 한 패스가 확정하는 쪽은 마지막 비교까지 참여하며 큰 값을 모아 온 오른쪽 끝입니다. 이 차이를 알아야 첫 패스 뒤 전체 배열이 정렬됐다고 오해하지 않습니다.

예제 함수는 유한한 Number로만 채워진 배열을 받아 복사본을 정렬합니다. 원본 배열은 유지하고 오름차순의 새 배열을 반환합니다. 빈 배열과 한 원소 배열은 비교 없이 복사본을 반환하며 음수와 중복값도 같은 비교 규칙을 따릅니다. NaN, 무한대, 문자열, 빈 칸 있는 배열은 정렬 전 거절합니다.

한 패스마다 정렬하지 않은 구간이 줄어듭니다

첫 패스의 마지막 교환은 4와 1입니다. 결과에서 1이 인덱스 2에 왔으므로, 가장 작은 값은 한 패스에 맨 앞으로 오지 못합니다. 다음 패스는 확정된 4를 제외한 앞의 세 값만 비교합니다. 마지막으로 확정되지 않은 두 값을 비교하면 모든 위치가 정리됩니다. end를 줄이는 이유는 단순한 횟수 조절이 아니라 이미 확정된 구간을 다시 만질 필요가 없기 때문입니다.

교환이 없는 패스에서는 바로 끝낼 수 있습니다

한 패스 동안 교환이 한 번도 없었다면 비교한 모든 이웃이 이미 오름차순입니다. 확정된 뒤쪽 구간도 정렬되어 있으므로 전체가 정렬된 상태입니다. 코드의 changed는 이번 패스에서 교환이 있었는지만 기억하며, 패스가 시작할 때마다 false로 초기화합니다. 이전 패스의 교환 기록을 계속 유지하면 정렬된 뒤에도 조기 종료하지 못합니다.

처음부터 정렬된 [1, 2, 3, 4]는 한 패스의 세 비교 후 끝나므로 최선 시간은 O(n)입니다. 거꾸로 된 입력처럼 교환이 계속 필요하면 비교 수는 (n - 1) + (n - 2) + … + 1로 O(n²)입니다. 조기 종료를 넣었다고 모든 입력이 선형 시간이 되는 것은 아닙니다.

비교에 >를 사용하므로 같은 값끼리는 자리를 바꾸지 않습니다. 항목에 별도 식별자가 있다고 생각하면 같은 키의 처음 순서가 유지되는 안정 정렬입니다. 현재 함수의 입력은 숫자 배열이라 식별자를 직접 받지는 않지만, 왜 같은 경우 교환하지 않는지 이해하면 객체 정렬로 확장할 때의 기준을 알 수 있습니다.

인덱스 경계와 복사 공간을 따로 셉니다

안쪽 반복문은 j가 end보다 작을 때만 실행합니다. 오른쪽 이웃으로 a[j + 1]을 읽으므로 j가 end와 같아지면 이미 정해 둔 구간 밖을 비교하게 됩니다. 비교 대상이 두 원소라는 사실에서 마지막 j의 범위가 나옵니다. 바깥 반복문도 end가 1일 때 마지막 두 원소를 비교한 뒤 끝납니다.

정렬 작업 자체는 값 교환을 위한 임시 공간만 필요하지만, 이 예제는 입력을 유지하기 위해 길이 n의 복사본을 만듭니다. 반환 배열을 포함한 추가 공간은 O(n)입니다. 다른 설명에서 버블 정렬 공간이 O(1)이라고 해도 충돌하는 것은 아닙니다. 그 분석은 원본 배열을 직접 바꾸는 구현을 기준으로 합니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function copyFiniteNumbers(values) {
  if (!Array.isArray(values)) throw new TypeError('숫자 배열이 필요합니다.');
  for (let i = 0; i < values.length; i++) {
    if (!Object.hasOwn(values, i) || !Number.isFinite(values[i])) {
      throw new TypeError('빈 칸 없는 유한 숫자 배열이 필요합니다.');
    }
  }
  return values.slice();
}

function bubbleSort(values) {
  const a = copyFiniteNumbers(values);
  for (let end = a.length - 1; end > 0; end--) {
    let changed = false;
    for (let j = 0; j < end; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        changed = true;
      }
    }
    if (!changed) break;
  }
  return a;
}

const input = [4, 2, 3, 1];
console.log(JSON.stringify(bubbleSort(input)));
console.log(JSON.stringify(input));
console.log(JSON.stringify(bubbleSort([])));

node javascript-bubble-sort-passes.mjs

[1,2,3,4]
[4,2,3,1]
[]

비용과 적용 범위

시간: 최선 O(n), 평균·최악 O(n²)

공간: O(n)

분석 조건: 빈 칸 없는 유한 숫자 배열을 복사해 반환합니다. 조기 종료가 있으며, 공간에는 반환 복사본을 포함합니다. 입력을 직접 정렬할 때의 교환 보조 공간은 O(1)입니다.

직접 확인해 보기

[3, 2, 1]을 왼쪽부터 한 패스만 비교하면 어떤 배열이 되나요? 아직 전체 정렬이 아닌 이유도 설명해 보세요.

함께 읽을 글

• JavaScript 배열: 인덱스 조회와 삽입·삭제 비용 — 값을 교환하는 비용과 복사본을 만드는 비용을 구분합니다.
• 완전탐색과 쌍 비교: 중복 없는 후보 열거와 순위 계산 — 이중 반복문이 실제로 비교하는 쌍과 범위를 분석합니다.

참고 자료

• Competitive Programmer’s Handbook — Sorting — 정렬 장의 버블 정렬, 병합 정렬 및 비교 정렬의 시간 분석을 참고했습니다. 예제와 추적 설명은 직접 작성했습니다.