버블정렬 알고리즘

프로그래밍 입문자나 컴퓨터 공학 전공생이 알고리즘을 학습할 때 가장 먼저 접하게 되는 것이 바로 정렬(Sorting)입니다. 데이터를 순서대로 나열하는 것은 데이터 처리의 효율성을 높이는 가장 기초적인 작업이기 때문입니다. 그중에서도 버블 정렬(Bubble Sort)은 구현이 매우 간단하고 직관적이어서 알고리즘적 사고를 기르는 데 최적의 예제입니다. 비록 현업의 대용량 데이터 처리에는 효율성 문제로 잘 사용되지 않지만, 버블 정렬의 동작 방식과 시간 복잡도를 이해하는 것은 향후 퀵 정렬, 병합 정렬 등 고급 알고리즘을 이해하는 필수 기반이 됩니다. 이번 글에서는 버블 정렬의 핵심 원리부터 파이썬(Python) 코드 구현, 그리고 성능 최적화 방법까지 심도 있게 다뤄보겠습니다.

1. 버블 정렬(Bubble Sort)의 핵심 개념과 원리

버블 정렬은 서로 인접한 두 원소의 크기를 비교하여, 정렬 기준(오름차순 또는 내림차순)에 맞지 않을 경우 자리를 교환(Swap)하는 알고리즘입니다. 이 과정에서 더 큰 값(또는 작은 값)이 마치 물속의 거품이 수면 위로 올라오는 것처럼 뒤쪽으로 이동한다고 하여 '버블 정렬'이라는 이름이 붙여졌습니다.

1-1. 알고리즘 동작 프로세스

오름차순 정렬을 기준으로 설명하면 다음과 같은 규칙으로 동작합니다.

1회전(Pass 1): 첫 번째 원소부터 마지막 원소까지 인접한 두 수를 비교하며, 앞의 수가 뒤의 수보다 크면 자리를 바꿉니다. 이 과정이 끝나면 배열에서 가장 큰 수가 맨 뒤로 이동하여 고정됩니다.
2회전(Pass 2): 다시 처음부터 비교를 시작하되, 맨 뒤에 고정된 원소는 제외합니다. 이 과정이 끝나면 두 번째로 큰 수가 뒤에서 두 번째 자리에 고정됩니다.
반복: 정렬해야 할 원소가 1개 남을 때까지 위 과정을 반복합니다.

1-2. 주요 특징

제자리 정렬(In-place Sorting): 데이터를 교환하는 과정에서 별도의 추가 메모리 공간이 거의 필요하지 않습니다.
안정 정렬(Stable Sort): 중복된 값이 있을 경우, 기존의 순서가 유지됩니다.
단순성: 구현이 매우 쉬워 소스 코드가 직관적입니다.

2. 버블 정렬 코드 구현 (Python 예제)

가장 대중적인 언어인 파이썬을 사용하여 버블 정렬을 구현해 보겠습니다. 핵심은 이중 반복문(Nested Loop)을 사용하는 것입니다.

2-1. 기본 구현 코드

아래 코드는 리스트 `arr`을 오름차순으로 정렬하는 가장 기본적인 형태입니다.

def bubble_sort(arr):
    n = len(arr) # 리스트의 길이
    
    # 배열의 모든 요소를 순회 (총 회전 수)
    for i in range(n):
        
        # 마지막 i개의 요소는 이미 정렬되어 있으므로 제외
        # j는 0부터 n-i-1까지 반복
        for j in range(0, n - i - 1):
            
            # 현재 요소가 다음 요소보다 크다면 위치 교환 (Swap)
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                
    return arr

# 테스트 데이터 실행
data = [64, 34, 25, 12, 22, 11, 90]
print("정렬 전:", data)
sorted_data = bubble_sort(data)
print("정렬 후:", sorted_data)

위 코드에서 `range(0, n - i - 1)` 부분이 중요합니다. `i`가 증가할수록 뒤쪽의 정렬된 요소들이 늘어나므로, 불필요한 비교를 줄이기 위해 내부 루프의 범위를 줄여나가는 것입니다.

3. 성능 분석: 시간 복잡도와 한계

개발자 면접이나 정보처리기사 시험 등에서 가장 자주 묻는 것이 바로 정렬 알고리즘의 시간 복잡도(Time Complexity)입니다. 버블 정렬은 효율성 면에서 어떤 점수를 받을까요?

3-1. 시간 복잡도 (Big-O Notation)

최악의 경우 (Worst Case): 데이터가 역순으로 정렬되어 있을 때입니다. 비교 횟수는 `N*(N-1)/2`가 되며, 이는 O(N²)로 표기합니다. 데이터가 10,000개라면 약 1억 번의 연산이 필요하므로 매우 느립니다.
평균적인 경우 (Average Case): 무작위로 섞여 있을 때도 역시 O(N²)의 복잡도를 가집니다.
최선의 경우 (Best Case): 이미 정렬되어 있는 경우, 최적화된 코드를 사용하면 O(N)이 가능하지만 일반적인 구현에서는 여전히 O(N²)입니다.

3-2. 공간 복잡도

주어진 배열 안에서 교환(Swap)만 이루어지므로 공간 복잡도는 O(1)입니다. 이는 메모리 자원이 극도로 제한된 임베디드 환경 등에서는 장점이 될 수 있습니다.

4. 고급 테크닉: 최적화된 버블 정렬 (Optimized Bubble Sort)

기본 버블 정렬은 데이터가 이미 정렬되어 있어도 끝까지 루프를 돕니다. 이를 개선하기 위해 '교환 발생 여부(Flag)'를 체크하는 로직을 추가할 수 있습니다.

def optimized_bubble_sort(arr):
    n = len(arr)
    
    for i in range(n):
        swapped = False # 교환 발생 여부를 체크하는 플래그
        
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True # 교환이 일어났음을 표시
        
        # 내부 루프에서 단 한 번도 교환이 없었다면, 이미 정렬된 상태임
        if not swapped:
            break # 조기 종료
            
    return arr

이 코드를 사용하면 이미 정렬된 데이터가 입력되었을 때, 1회전만 수행하고 즉시 종료하므로 불필요한 연산을 획기적으로 줄일 수 있습니다.

[핵심 요약] 버블 정렬 마스터하기
1. 원리: 인접한 두 원소를 비교/교환하며, 매 회전마다 가장 큰 수를 맨 뒤로 보낸다.
2. 성능: 시간 복잡도는 O(N²)로 비효율적이나, 구현이 쉽고 코드가 직관적이다.
3. 팁: `swapped` 변수를 활용하여 정렬이 완료되면 반복문을 조기 종료시키는 최적화가 가능하다.

코드 아카이브