Ch.8 정렬과 탐색

O(n²) 정렬 — Bubble, Selection, Insertion

Bubble, Selection, Insertion Sort의 동작 원리를 설명한다세 가지 정렬의 시간/공간 복잡도를 비교한다

가장 직관적인 정렬, 하지만 가장 느리다

카드를 손에 들고 정리하는 방법을 떠올려보세요. 하나씩 비교하며 자리를 바꾸는 것 — 이것이 O(n²) 정렬의 본질입니다.

왜 이 단순한 정렬들을 알아야 할까? 어차피 면접에서는 빠른 정렬을 쓰는데?

O(n²) 정렬을 이해해야 O(n log n) 정렬이 왜 빠른지 비교 설명할 수 있습니다.

lightbulb

핵심 개념

Bubble Sort

인접한 두 원소를 비교하여 큰 값을 뒤로 보내는 정렬

안정 정렬(Stable)

같은 값의 원소가 원래 순서를 유지하는 정렬

article

핵심 내용

거품이 수면 위로 올라오듯 큰 값이 뒤로 밀려납니다

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:  # 최적화: 교환 없으면 종료
            break
    return arr

`swapped` 플래그로 이미 정렬된 경우 조기 종료할 수 있습니다 — 최선 O(n)

Bubble Sort가 배열을 어떻게 정렬하는지 추적합니다

매 패스마다 가장 큰 값이 배열 끝으로 이동합니다

매 라운드마다 가장 작은 값을 찾아 앞쪽에 배치합니다

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

Selection Sort 특성: • 시간: 항상 O(n²) — 최선도 O(n²) • 공간: O(1) — in-place • 불안정 정렬 — swap 시 순서 깨질 수 있음 • swap 횟수 최소: 최대 n번만 교환

Selection Sort는 swap 횟수가 적어 교환 비용이 클 때 유리합니다

카드를 한 장씩 받아 올바른 위치에 삽입하는 방식입니다

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 오른쪽으로 밀기
            j -= 1
        arr[j + 1] = key  # 삽입
    return arr

Insertion Sort 특성: • 시간: 최선 O(n), 평균/최악 O(n²) • 공간: O(1) — in-place • 안정 정렬 • 거의 정렬된 데이터에서 매우 빠름

Python의 Timsort가 Insertion Sort를 내부적으로 사용하는 이유: 소규모·거의 정렬된 구간에 최적

세 가지 O(n²) 정렬을 한눈에 비교합니다

| 정렬 | 최선 | 평균 | 최악 | 안정 | 특징 | |------|------|------|------|------|------| | Bubble | O(n) | O(n²) | O(n²) | ✅ | 교환 기반 | | Selection | O(n²) | O(n²) | O(n²) | ❌ | swap 최소 | | Insertion | O(n) | O(n²) | O(n²) | ✅ | 거의 정렬 시 최적 |

면접 포인트: Insertion Sort가 실전에서 가장 유용합니다 — Timsort의 핵심 구성 요소!

이미 정렬된 배열에 대해 가장 빠르게 동작하는 O(n²) 정렬은?

Selection Sort는 안정 정렬이다

O(n²) 정렬 마스터!

key

핵심 용어

⏱️

시간 복잡도

최선 O(n), 평균/최악 O(n²)

💾

공간 복잡도

O(1) — in-place

✅

안정 정렬

같은 값의 순서 유지

edit_note

정리 노트

O(n²) 정렬 3총사

핵심 비교

Bubble Sort: 인접 교환, 안정, 최선 O(n)
Selection Sort: 최솟값 선택, 불안정, swap 최소
Insertion Sort: 삽입 방식, 안정, 거의 정렬 시 최적

면접 팁

Timsort: Insertion + Merge의 하이브리드
안정 정렬: 같은 값의 원래 순서 유지 — DB 정렬 시 중요

★

O(n²) 정렬의 '왜 느린지'를 설명할 수 있어야 O(n log n) 정렬의 가치를 어필합니다!

image

시각 자료

다이어그램: ds-d61

check_circle

핵심 정리

1Bubble Sort — 인접 교환, 조기 종료 최적화
2Selection Sort — swap 최소, 불안정
3Insertion Sort — 거의 정렬 시 O(n), Timsort의 핵심

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작