버블 정렬: 인접 비교와 교환으로 구현하는 안정 정렬

오른쪽 끝에 정렬 구간을 쌓는 방식

버블 정렬은 서로 인접한 원소를 차례로 비교해 순서가 뒤집혀 있으면 교환한다. 한 번의 패스가 끝나면 그 범위에서 가장 큰 원소가 배열의 오른쪽 끝에 자리 잡고, 다음 패스에서는 그 원소를 제외한 범위만 처리한다.

비교 기반 정렬이며, 같은 키를 가진 원소의 상대 순서를 유지하는 안정 정렬이다. 추가 메모리는 O(1)만 사용한다. 최악과 평균 시간 복잡도는 O(n^2)이고, 교환이 없을 때 중단하는 조기 종료를 적용하면 최선의 경우 O(n)이다.

비교 범위가 줄어드는 이유

A[i]와 A[i+1]을 비교해 A[i] > A[i+1]이면 두 값을 교환한다. 한 패스에서는 최대 n-1번 비교하며, 교환 횟수는 입력 데이터의 분포에 따라 달라진다.

패스가 진행될수록 오른쪽 끝에는 이미 정렬이 끝난 원소가 쌓인다. 따라서 외부 루프가 한 번 돌 때마다 내부 비교 범위를 1씩 줄일 수 있다. 마지막 교환이 발생한 위치인 lastSwap을 기록하면, 다음 패스의 경계를 그 지점까지 더 좁힐 수 있다.

한 패스 동안 교환이 한 번도 없었다면 배열은 이미 정렬된 상태다. 이때 즉시 종료하는 플래그가 조기 종료의 기준이 된다.

경계 축소와 조기 종료 흐름

입력 배열 A와 길이 n이 주어지면, 먼저 swapped=false, lastSwap=0으로 초기화한다. 비교 범위 안에서 인접 원소를 검사하고 순서가 어긋난 경우 교환한 뒤 lastSwap을 갱신한다. 교환이 없으면 종료하고, 있었다면 마지막 교환 위치를 다음 비교 경계로 사용한다.

⤢✕

C와 Python 구현

오름차순 정렬을 전제로 하며, 비교 연산자 >가 총순서를 정의한다. 실행 환경은 C11(gcc/clang), Python 3.10+이다.

C 기본형과 경계 축소형

// C11, gcc -O2 bubble.c -o bubble
#include <stddef.h>

static inline void swap_int(int* a, int* b) {
    int t = *a; *a = *b; *b = t;
}

// 기본형: 이중 루프, 패스마다 범위 축소
void bubble_sort_basic(int a[], size_t n) {
    if (!a || n < 2) return;
    for (size_t pass = 0; pass < n - 1; ++pass) {
        for (size_t j = 0; j < n - 1 - pass; ++j) {
            if (a[j] > a[j + 1]) swap_int(&a[j], &a[j + 1]);
        }
    }
}

// 최적형: 조기 종료 + 마지막 교환 위치로 경계 축소
void bubble_sort(int a[], size_t n) {
    if (!a || n < 2) return;
    size_t bound = n;
    while (bound > 1) {
        size_t lastSwap = 0;
        for (size_t i = 1; i < bound; ++i) {
            if (a[i - 1] > a[i]) {
                swap_int(&a[i - 1], &a[i]);
                lastSwap = i;
            }
        }
        if (lastSwap == 0) break;  // 조기 종료
        bound = lastSwap;
    }
}

Python 경계 축소형

# Python 3.10+
from typing import List

def bubble_sort(a: List[int]) -> List[int]:
    n = len(a)
    bound = n
    while bound > 1:
        last_swap = 0
        for i in range(1, bound):
            if a[i-1] > a[i]:
                a[i-1], a[i] = a[i], a[i-1]
                last_swap = i
        if last_swap == 0:
            break
        bound = last_swap
    return a

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

구현에서 놓치기 쉬운 경계

교환 과정에서 임시값을 잘못 대입하면 값이 덮어써진다. temp=item[t]; item[t]=item[t+1]; item[t]=temp;의 마지막 대입은 item[t+1]=temp여야 한다.

A[i-1]에 접근하므로 i는 1부터 시작해야 한다. i=0이면 범위 오류가 발생한다. 내부 루프 상한은 n-1-pass 또는 bound-1 형태로 두어 이미 정렬된 구간을 다시 비교하지 않는다. 패스 카운터는 내부 비교가 끝난 뒤 증가시켜야 범위 축소가 의도대로 반영된다.

void bubble_sort_flag(int A[], int n) {
    if (!A || n < 2) return;
    int loop = 0;
    int swapped = 1;
    while (swapped) {
        swapped = 0;
        for (int i = 1; i < n - loop; ++i) {  // i는 1부터
            if (A[i - 1] > A[i]) {
                int t = A[i];
                A[i] = A[i - 1];
                A[i - 1] = t;  // A[i+1]가 아님에 주의
                swapped = 1;
            }
        }
        ++loop;  // 패스 종료 후 증가
    }
}

선택하기 좋은 입력과 성능 한계

버블 정렬은 비교·교환 정렬의 원리, 안정성, 조기 종료를 설명하거나 디버깅할 때 유용하다. 코드 크기가 중요하고 N이 매우 작은 컬렉션을 다루는 소형 임베디드·펌웨어 환경에서도 선택할 수 있다. 거의 정렬된 데이터에서는 조기 종료를 이용한 간단한 사전 정리 단계로 쓸 수 있다.

이미 정렬에 가까운 입력에서는 비교 n-1회, 스왑 0회로 최선 O(n)이 가능하다. 평균과 최악은 O(n^2)이며, 비교는 약 n(n-1)/2회이고 스왑 횟수는 데이터 분포에 따라 달라진다. 공간 복잡도는 O(1)이다.

구현이 단순하고 유지보수와 디버깅이 쉽다는 장점이 있지만, 대규모 데이터셋에는 병합 정렬, 퀵 정렬, 힙 정렬 등이 더 적합하다. 거의 정렬된 입력에서는 삽입 정렬이 더 유리할 수 있다.

알고리즘	평균/최악 성능	안정성	공간 복잡도	적응성(조기 종료)	운영 편의
버블 정렬	O(n^2)/O(n^2)	예	O(1)	가능(flag)	매우 단순
선택 정렬	O(n^2)/O(n^2)	아니오	O(1)	불가	단순
삽입 정렬	O(n^2)/O(n^2)	예	O(1)	높음(거의 정렬 시 O(n))	단순