알고리즘SortO(n²)Comparison

버블 정렬

인접한 두 원소를 반복 비교·교환하는 기초 정렬

시각화 로드 중...

알고리즘 복잡도

최선O(n)
평균O(n²)
최악O(n²)
공간O(1)
안정 정렬 ✓

개요

Algorithm Overview

버블 정렬(Bubble Sort)은 인접한 두 원소를 비교하여 순서가 맞지 않으면 서로 교환(Swap)하는 과정을 반복하며, 각 회차마다 가장 큰 원소가 거품(Bubble)처럼 배열의 맨 뒤로 밀려 올라가는 기초 비교 정렬 알고리즘입니다.

01

버블 정렬의 핵심 동작 원리

  • 인접 원소 비교 및 교환: 배열의 첫 번째 원소부터 마지막 미정렬 원소까지 인접한 두 값을 비교하여 앞의 값이 더 크면 교환합니다.
  • 패스(Pass)별 최댓값 확정: 1회 순회가 끝날 때마다 현재 미정렬 구간의 최댓값이 배열 우측 끝에 영구 고정됩니다.
  • 조기 종료 최적화 (Early Exit): 한 패스 동안 단 한 번의 원소 교환도 발생하지 않았다면 이미 전체 배열이 정렬된 상태이므로 루프를 즉시 탈출하여 최선 $O(n)$ 시간에 종료합니다.
02

입력별 실행 추적

예를 들어 [3, 1, 2]를 오름차순으로 정렬할 때 첫 패스에서 (3, 1)을 비교·교환하여 [1, 3, 2], 이어서 (3, 2)를 비교·교환하여 [1, 2, 3]이 됩니다. 첫 패스의 비교 2회, 교환 2회로 최댓값 3이 확정됩니다. 조기 종료를 사용하는 구현에서는 다음 패스에서 (1, 2)를 비교하고 교환이 없으므로 종료합니다. 총 비교 3회, 교환 2회입니다.

입력이 [1, 2, 3]이면 첫 패스에서 2회 비교, 0회 교환 후 종료합니다. 반면 [3, 2, 1]은 첫 패스에서 [2, 1, 3], 두 번째 패스에서 [1, 2, 3]이 되어 비교 3회, 교환 3회가 발생합니다. 동일한 배열 길이라도 입력 순서에 따라 교환 비용이 달라집니다.

03

복잡도 및 특성

  • 시간 복잡도: 최선 $O(n)$ (이미 정렬된 경우), 평균 및 최악 $O(n^2)$ (역순 정렬인 경우)
  • 공간 복잡도: $O(1)$ 보조 메모리만을 사용하는 제자리 정렬(In-Place Sort)
  • 안정 정렬 (Stable Sort): 동일한 값을 가진 원소 간에는 스왑이 일어나지 않으므로 상대적 순서가 보존됩니다.

학습 목표

  • 각 패스가 끝날 때 확정되는 배열 구간을 설명할 수 있다.
  • 비교 횟수와 교환 횟수가 입력 배열에 따라 달라지는 이유를 구분할 수 있다.
  • 조기 종료가 최선 시간 복잡도를 O(n)으로 만드는 조건을 설명할 수 있다.

자주 하는 오해

  • 최선 O(n)은 교환이 없는 패스를 감지하는 조기 종료 구현에서만 성립합니다.
  • 버블 정렬은 인접 원소만 교환하며, 한 패스마다 확정되는 것은 미정렬 구간의 최댓값입니다.

핵심 정리

  • 길이 n의 역순 배열은 n(n-1)/2번 비교하고 모든 비교에서 교환합니다(표준 최적화 구현 기준).
  • 이미 정렬된 배열은 첫 패스에서 n-1번 비교하고 교환 없이 종료합니다(조기 종료 적용 시).

학습 확인

문제 1

[3, 1, 2]에 버블 정렬 첫 번째 패스를 적용하면 배열은?

문제 2

조기 종료를 적용한 버블 정렬에서 이미 정렬된 길이 n 배열의 비교 횟수는?

핵심 단계

  1. 1

    0번째부터 (n-2)번째 원소까지 인접한 다음 원소와 비교

  2. 2

    arr[i] > arr[i+1]이면 두 원소 교환 (swap)

  3. 3

    한 패스 완료 후 배열 끝에 최대값 고정

  4. 4

    다음 패스는 마지막 고정 원소를 제외하고 반복

  5. 5

    교환이 한 번도 없으면 이미 정렬됨 → 조기 종료

핵심 개념 및 실무 적용 분야

✓알고리즘 교육 및 정렬 개념 입문
✓소규모 데이터 또는 거의 정렬된 데이터

참고 자료

개념과 기술 규격을 추가로 확인할 수 있는 외부 자료입니다. 시각화는 교육 목적에 맞게 일부 절차를 단순화할 수 있습니다.