정렬 알고리즘 — 버블, 선택, 병합

이 토픽을 마치면

세 가지 정렬 알고리즘의 작동 방식을 설명할 수 있고, 각각의 시간 복잡도와 장단점을 비교할 수 있습니다.

왜 정렬을 배우는가

정렬은 프로그래밍에서 가장 기본적이면서도 가장 많이 연구된 문제입니다. 실무에서 직접 정렬 알고리즘을 구현하는 경우는 드물지만(Python의 sorted()를 쓰면 됩니다), 정렬 알고리즘을 공부하면 알고리즘적 사고 방식이 훈련됩니다 — 문제를 어떻게 쪼개고, 반복하고, 최적화하는가.

버블 정렬 — 가장 직관적

인접한 두 원소를 비교해서, 순서가 잘못되면 교환합니다. 이것을 전체가 정렬될 때까지 반복합니다.

python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# [5, 3, 8, 1, 2] → [3, 5, 1, 2, 8] → ... → [1, 2, 3, 5, 8]

작동 과정 (한 회전):

text

[5, 3, 8, 1, 2]
 5>3 → 교환 → [3, 5, 8, 1, 2]
 5<8 → 유지 → [3, 5, 8, 1, 2]
 8>1 → 교환 → [3, 5, 1, 8, 2]
 8>2 → 교환 → [3, 5, 1, 2, 8]  ← 8이 맨 뒤로

큰 값이 거품처럼 위로 "떠오르는" 모습이라 버블 정렬입니다. 시간 복잡도: O(n²). 이해하기 쉽지만 느립니다.

선택 정렬 — 최솟값을 골라 앞으로

전체에서 가장 작은 값을 찾아 맨 앞으로 보냅니다. 그다음 나머지에서 가장 작은 값을 찾아 두 번째로 보냅니다. 이것을 반복합니다.

python

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

작동 과정:

text

[5, 3, 8, 1, 2]
 최소=1 → [1, 3, 8, 5, 2]
 최소=2 → [1, 2, 8, 5, 3]
 최소=3 → [1, 2, 3, 5, 8]
 완료

시간 복잡도: O(n²). 버블 정렬과 같지만, 교환 횟수가 적어서 실제로는 약간 더 빠릅니다.

병합 정렬 — 분할 정복

아이디어: 리스트를 반으로 나누고, 각각 정렬한 뒤, 합칩니다.

python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # 왼쪽 절반 정렬
    right = merge_sort(arr[mid:])  # 오른쪽 절반 정렬
    
    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

작동 과정:

text

[5, 3, 8, 1, 2]
    ↙         ↘
[5, 3, 8]   [1, 2]
  ↙   ↘       ↓
[5] [3,8]  [1, 2]
     ↓       ↓
[5] [3,8] [1,2]
  ↘  ↙      ↓
[3,5,8]  [1,2]
    ↘     ↙
[1, 2, 3, 5, 8]

시간 복잡도: O(n log n). 매번 반으로 나누므로(log n 단계) × 각 단계에서 n번 비교 = O(n log n). 이것이 비교 기반 정렬의 이론적 최적값입니다.

성능 비교

알고리즘	최선	평균	최악	안정성	추가 메모리
버블 정렬	O(n)	O(n²)	O(n²)	안정	O(1)
선택 정렬	O(n²)	O(n²)	O(n²)	불안정	O(1)
병합 정렬	O(n log n)	O(n log n)	O(n log n)	안정	O(n)

안정(stable): 같은 값의 원래 순서가 유지됩니다. (예: 점수가 같은 학생의 이름 순서)
버블/선택은 추가 메모리가 필요 없지만(in-place), 병합은 새 리스트를 만들어야 합니다

10,000개 기준: 버블/선택 ≈ 1억 번 연산, 병합 ≈ 13만 번. 차이가 770배입니다.

실무에서는 어떻게 쓰는가

python

# Python 내장 — Timsort (병합 + 삽입 정렬 하이브리드)
numbers = [5, 3, 8, 1, 2]
sorted(numbers)           # 새 리스트 반환
numbers.sort()             # 원본 정렬

# 기준 지정
students = [("김훈", 90), ("이수", 85), ("박진", 95)]
sorted(students, key=lambda s: s[1])  # 점수순
sorted(students, key=lambda s: s[1], reverse=True)  # 내림차순

Python의 sorted()는 Timsort 알고리즘을 사용합니다. 병합 정렬과 삽입 정렬의 장점을 결합한 것으로, 실제 데이터에서 매우 효율적입니다. 직접 정렬을 구현할 필요가 없는 이유입니다.

핵심 정리

세 알고리즘은 같은 문제를 다른 접근으로 풀고, 그 차이가 O(n²) vs O(n log n)이라는 극적인 성능 차이로 나타납니다. 이것이 알고리즘을 공부하는 이유입니다 — 같은 결과를 내더라도 어떻게 도달하느냐에 따라 1000배 이상 차이가 납니다. 정렬뿐 아니라 검색, 그래프, 최적화 등 모든 알고리즘 문제에 같은 원리가 적용됩니다.