D-1: 정렬 ① 비교 기반 정렬 — O(n²)를 O(n log n)으로 끌어내린다

안녕하세요, 홍순구 튜터입니다. 지난 시간까지 우리는 데이터를 담는 그릇을 다 만들었습니다. 카테고리 B에서 선형 자료구조(스택·큐·연결 리스트·해시)를, 카테고리 C에서 비선형 자료구조(트리·힙·그래프)를 손으로 짰죠. 이제 그릇을 넘어, 그 위에서 데이터를 다루는 알고리즘으로 넘어옵니다. 카테고리 D의 첫 주제는 정렬(sort)입니다.

정렬은 코딩테스트에서 가장 기본이 되는 무기입니다. 그 자체로 문제가 되기도 하지만, 더 중요한 건 정렬이 다른 알고리즘의 발판이 된다는 거예요. 정렬된 배열이라야 절반씩 좁혀 찾는 이진 탐색(D-3)이 돌고, 양 끝에서 조여 오는 투 포인터(D-4)가 통합니다. "일단 정렬해 놓으면 풀리는" 문제가 정말 많습니다.

그런데 "정렬 좀 해 봐"라고 하면 보통 버블 정렬 하나만 떠오릅니다. 이게 왜 느린지, 그리고 어떻게 병합·퀵 정렬로 훨씬 빠르게 끌어내리는지를 오늘 직접 짜 보며 익힙니다. 정렬 종류가 많아 두 시간에 나눠 배우는데, 오늘은 그중 비교 기반 정렬 여섯 가지입니다. 다음 시간엔 비교를 아예 안 하는 정렬과 실전 내장 정렬을 봅니다.

 오늘의 여정 — 정렬 ①, 비교로 줄 세우는 여섯 가지

   느린 정렬 (O(n²))       빠른 정렬 (O(n log n))      고르는 눈
   버블·선택·삽입            병합 (분할정복)             입력 크기로 판단
   비교하고 자리 바꾸기       퀵 (피벗 분할)              세 잣대로 견주기
                           힙 (C-2 회수)

💡 오늘 수업의 핵심 — "소박한 O(n²) 정렬 셋을 이해하고, 분할정복으로 O(n log n)까지 끌어내린 뒤, 병합·퀵·힙을 세 잣대로 견줘 고른다"

🎯 학습 목표

• 버블·선택·삽입 정렬이 왜 O(n²)인지 이해하고, 안정성·제자리·비교라는 세 잣대로 정렬을 본다.
• 병합·퀵 정렬을 분할정복으로 직접 구현하고, O(n log n)이 나오는 이유를 설명한다.
• 힙 정렬로 C-2의 힙을 회수하고, 입력 크기를 보고 어떤 정렬을 쓸지 빅오로 고른다.

Step 1: "왜 줄을 세우나 — 정렬을 보는 세 잣대"

정렬이 뭔지는 다 압니다. 뒤죽박죽인 데이터를 크기순으로 줄 세우는 거죠. [5, 2, 9, 1]을 [1, 2, 5, 9]로 만드는 것. 그런데 왜 이걸 이렇게 열심히 배울까요?

정렬은 그 자체보다 "정렬한 다음에 뭘 할 수 있느냐"가 진짜 힘입니다. 뒤섞인 배열에서 특정 값을 찾으려면 처음부터 끝까지 훑어야 해서 O(n)이지만, 정렬해 두면 절반씩 좁혀 O(log n)에 찾습니다(이진 탐색, 다음 시간에 배웁니다). 중복 제거, 두 번째로 큰 값 찾기, 겹치는 구간 병합 같은 문제도 정렬 한 번이면 훨씬 쉬워져요. 그래서 "막히면 일단 정렬해 보라"는 말이 코테의 격언입니다.

정렬 알고리즘은 종류가 많은데, 앞으로 하나하나 볼 때마다 늘 세 가지 잣대로 견주겠습니다. 이 세 잣대가 오늘 내내 비교표의 기둥이 됩니다.

• 안정성(stable): 값이 같은 원소들의 원래 순서가 정렬 뒤에도 지켜지는가.
• 제자리(in-place): 입력 배열 말고 추가로 쓰는 공간이 O(1)로 적은가.
• 비교(comparison): 원소끼리 크기를 직접 비교해서 순서를 정하는가.

안정성이 조금 낯설 텐데, 그림으로 보면 금방입니다. 이름과 점수 묶음을 점수순으로 정렬한다고 해 봅시다.

 안정 정렬 — 점수가 같은 (민지 80)·(수현 80)의 원래 순서가 유지된다

  입력:   (민지,80)  (지훈,95)  (수현,80)  (예린,70)
                      점수순 정렬 ↓
  안정:   (예린,70)  (민지,80)  (수현,80)  (지훈,95)
                     └ 80 동점: 민지 → 수현 (입력 순서 그대로)
  불안정: (예린,70)  (수현,80)  (민지,80)  (지훈,95)
                     └ 80 동점: 수현 → 민지 (순서가 뒤바뀜)

동점일 때 원래 순서가 지켜지면 안정 정렬입니다. "점수순으로 정렬하되 같은 점수는 먼저 등록한 사람이 위로" 같은 요구가 흔해서, 안정성은 실전에서 꽤 중요합니다.

오늘 배울 여섯 정렬은 전부 세 번째 잣대, 비교 기반입니다. 원소끼리 크고 작음을 따져 순서를 정해요. 비교를 아예 하지 않고 O(n)까지 내려가는 계수·기수 정렬은 다음 시간에 만납니다.

🎯 코테에서는 정렬 자체를 직접 짜라는 문제보다, "정렬한 뒤에 무엇을 하느냐"가 핵심인 경우가 훨씬 많습니다. 좌표를 정렬해 겹침을 확인하거나, 정렬 후 이진 탐색·투 포인터로 O(n²)를 O(n log n)으로 줄이는 식이죠. 그래서 정렬은 "풀이의 1단계"로 깔고 갑니다.

💡 한 줄 정리

정렬은 탐색·투 포인터 같은 뒷 알고리즘의 발판이고, 모든 정렬은 안정성·제자리·비교라는 세 잣대로 견준다.

Step 2: "O(n²) 정렬 삼형제 — 버블·선택·삽입"

가장 소박한 정렬 셋부터 봅시다. 버블, 선택, 삽입. 셋 다 "비교하고 자리를 바꾼다"는 발상이 비슷하고, 셋 다 시간 복잡도가 O(n²)입니다. 왜 셋이 다 O(n²)인지, 그런데도 미묘하게 어떻게 다른지를 보는 게 이 Step의 목표예요.

버블 정렬 — 큰 값이 거품처럼 뒤로

인접한 두 원소를 비교해서, 왼쪽이 더 크면 자리를 바꿉니다. 이걸 왼쪽부터 끝까지 반복하면 한 바퀴에 가장 큰 값이 물거품처럼 맨 뒤로 떠올라요.

 버블 정렬 한 바퀴 — [5, 2, 9, 1] 에서 가장 큰 9가 뒤로

  [5, 2, 9, 1]  →  5 > 2, 교환  →  [2, 5, 9, 1]
  [2, 5, 9, 1]  →  5 < 9, 유지  →  [2, 5, 9, 1]
  [2, 5, 9, 1]  →  9 > 1, 교환  →  [2, 5, 1, 9]
                                   9가 맨 뒤에 안착 ┘

한 바퀴에 제일 큰 값 하나가 뒤로 갑니다. 다음 바퀴는 이미 자리 잡은 맨 뒤 하나를 빼고 돌면 돼요. n개를 정렬하려면 이런 바퀴를 약 n번 돌고, 각 바퀴가 약 n번 비교하니 O(n²)입니다.

# algorithms/sorting.py
def bubble_sort(arr):
    a = list(arr)
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):          # 이미 뒤로 간 i개는 건드리지 않는다
            if a[j] > a[j + 1]:             # 왼쪽이 더 크면 자리를 바꿔 뒤로 민다
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:                     # 한 바퀴 동안 교환 0회 → 이미 정렬됨
            break
    return a

swapped 플래그 한 줄이 작은 최적화입니다. 한 바퀴를 다 돌았는데 교환이 한 번도 없었다면, 이미 정렬이 끝난 거라 곧장 멈춥니다. 덕분에 이미 정렬된 입력은 한 바퀴만 돌고 끝나 O(n)이 돼요. 그리고 버블 정렬은 값이 같을 때는 교환하지 않으니(>로만 바꿈) 안정 정렬입니다.

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

이번엔 남은 부분에서 가장 작은 값을 골라 맨 앞으로 보냅니다. 맨 앞에 놓을 최솟값을 전부 훑어 찾고, 그다음에 놓을 최솟값을 또 찾고, 이렇게 반복해요.

def selection_sort(arr):
    a = list(arr)
    n = len(a)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):           # i 뒤에서 가장 작은 값의 위치를 찾는다
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]  # 찾은 최솟값을 i 자리로 (한 번만 교환)
    return a

선택 정렬의 특징은 교환이 한 바퀴에 딱 한 번뿐이라는 겁니다. 최댓값을 찾는 동안 위치만 기억했다가, 마지막에 한 번만 맞바꿔요. 그래서 "쓰기(교환)가 비싼" 환경에 유리합니다. 대신 최솟값을 찾으려면 남은 전부를 매번 훑어야 해서, 입력이 이미 정렬돼 있어도 비교는 늘 n²/2번 — 최선도 O(n²)입니다. 그리고 멀리 있는 값과 통째로 자리를 바꾸다 보니 같은 값의 순서가 뒤집힐 수 있어 불안정합니다.

삽입 정렬 — 정렬된 앞부분에 끼워 넣기

세 번째는 삽입 정렬입니다. 카드를 손에 들고 정렬하는 방식과 똑같아요. 왼쪽은 늘 정렬된 상태로 두고, 새 카드(key)를 그 정렬된 부분의 알맞은 곳에 밀어 넣습니다.

def insertion_sort(arr):
    a = list(arr)
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:        # key보다 큰 값들을 오른쪽으로 한 칸씩 민다
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key                      # 큰 값들이 비켜준 자리에 key를 놓는다
    return a

삽입 정렬에는 남다른 강점이 하나 있습니다. key보다 큰 값들만 오른쪽으로 밀면 되니까, 입력이 거의 정렬돼 있으면 밀 일이 거의 없어 O(n)에 가까워요. 그래서 파이썬 내장 정렬(Timsort)도 작은 조각이나 거의 정렬된 부분은 삽입 정렬로 처리합니다. 이 이야기는 마지막 Step에서 다시 만나요. 같은 값은 앞뒤가 안 바뀌니 삽입 정렬도 안정 정렬입니다.

셋을 나란히 놓고 보면

셋을 표로 견주면 차이가 또렷해집니다.

셋 다 추가 공간 O(1)인 제자리 정렬입니다. 그리고 세 함수 모두 같은 답을 냅니다.

정렬([5, 2, 9, 1, 5, 6]) → [1, 2, 5, 5, 6, 9]   (세 정렬 모두 동일)

🎯 코테에서는 이 세 정렬을 실전에서 직접 쓰는 일은 드뭅니다(내장 정렬이 더 빠르니까요). 다만 "정렬을 직접 구현하라"거나 삽입 정렬의 동작을 묻는 문제가 나오고, 무엇보다 O(n²)가 왜 느린지를 몸으로 알아야 O(n log n)의 고마움을 압니다. 데이터가 아주 작거나(수십 개) 거의 정렬돼 있으면 삽입 정렬이 오히려 실용적일 때도 있어요.

💡 한 줄 정리

버블·선택·삽입은 모두 O(n²) 제자리 정렬이지만, 삽입 정렬만은 거의 정렬된 입력에서 O(n)으로 빨라지고 안정적이다.

Step 3: "나눠서 합친다 — 병합 정렬"

이제 O(n²)의 벽을 넘습니다. 첫 주자는 병합 정렬(merge sort)이에요. 발상이 아주 강력한데, "혼자 다 정렬하려니 O(n²)니까, 반으로 쪼개서 각각 정렬한 뒤 합치자"입니다.

이 발상에 이름이 있습니다. 분할정복(divide and conquer)이에요. 문제를 더 못 쪼갤 때까지 반씩 나누고(divide), 작은 답들을 합치며 되돌아온다(conquer)는 사고법입니다. 이 사고법 자체는 나중에 E-3에서 본격적으로 다루는데, 오늘은 정렬로 그 맛을 먼저 봅니다.

 병합 정렬 — [5, 2, 9, 1] 을 반씩 쪼갰다 다시 합친다

  분할 (내려가며 쪼갬)            병합 (올라오며 합침)
  [5, 2, 9, 1]                   [1, 2, 5, 9]
    ├ [5, 2]         →           [2, 5]
    │   ├ [5]                       [5]
    │   └ [2]                       [2]
    └ [9, 1]         →           [1, 9]
        ├ [9]                       [9]
        └ [1]                       [1]

원소가 하나가 될 때까지 쪼개면, 하나짜리는 그 자체로 이미 정렬된 상태입니다. 거기서부터 두 조각씩 합치며 올라와요.

def merge_sort(arr):
    a = list(arr)
    if len(a) <= 1:                         # 원소 0~1개는 이미 정렬된 상태 (종료 조건)
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])              # 왼쪽 절반을 정렬
    right = merge_sort(a[mid:])             # 오른쪽 절반을 정렬
    return merge(left, right)               # 정렬된 두 조각을 하나로 합친다

핵심은 "정렬된 두 조각을 하나로 합치는" merge입니다. 양쪽 맨 앞을 비교해서 작은 쪽을 먼저 담고, 담은 쪽 포인터만 한 칸 옮겨요. 두 조각이 이미 정렬돼 있으니 맨 앞만 봐도 충분합니다.

def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:            # 같을 때 왼쪽 먼저 → 안정성 보장
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])                # 한쪽이 남으면 통째로 이어 붙인다
    merged.extend(right[j:])
    return merged

left[i] <= right[j]에서 등호가 안정성의 비결입니다. 값이 같을 때 왼쪽(원래 앞에 있던) 조각을 먼저 담으니 순서가 지켜져요.

시간 복잡도가 왜 O(n log n)일까요? 쪼개는 깊이를 보면 됩니다. n개를 반씩 쪼개면 1이 될 때까지 약 log n번 쪼개집니다. 그리고 각 깊이에서 합치는 데 원소를 한 번씩 훑으니 O(n)이에요. 깊이(log n) × 각 깊이의 일(n) = O(n log n)입니다. 중요한 건 이게 최악에도 흔들리지 않는다는 점이에요. 어떤 입력이 와도 늘 반씩 쪼개지니까요. 대신 합칠 때 임시 리스트가 필요해 추가 공간을 O(n) 씁니다.

🎯 코테에서는 병합 정렬의 merge 단계는 그 자체로 자주 쓰입니다. "정렬된 두 배열을 합쳐라", "여러 정렬된 리스트를 병합하라" 같은 문제가 대표적이에요. 그리고 안정성이 필요하면서 최악의 성능도 보장돼야 할 때(O(n log n) 확정) 병합 정렬을 씁니다.

💡 한 줄 정리

병합 정렬은 반씩 쪼개 각각 정렬한 뒤 합치는 분할정복으로, 최악에도 O(n log n)을 보장하는 안정 정렬이다(공간 O(n)).

Step 4: "제자리에서 가른다 — 퀵 정렬"

병합 정렬은 O(n log n)을 보장하지만 임시 배열이 필요했죠. 퀵 정렬(quick sort)은 임시 배열 없이 배열 안에서 자리를 바꿔 가며 정렬합니다. 그래서 평균적으로 병합 정렬보다 빠르고, 실무 라이브러리들이 오래 애용해 온 정렬이에요.

발상은 이렇습니다. 피벗(pivot)이라는 기준값을 하나 정하고, 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 몰아요. 그러면 피벗은 정렬된 자기 자리에 딱 놓입니다. 그 좌우를 같은 방식으로 또 정렬하면 끝이에요.

 partition — 피벗 3을 기준으로 작은 것/큰 것 가르기  [5, 2, 9, 1, 6, 3]

  피벗 = 3 (맨 끝 원소)
  3 이하는 왼쪽으로, 3 초과는 오른쪽으로 몰면:

        [ 2, 1 ] [ 3 ] [ 5, 6, 9 ]
          작은 값   피벗    큰 값
                    3이 정렬된 제자리에 안착 ┘

  → 왼쪽 [2, 1] 과 오른쪽 [5, 6, 9] 를 각각 다시 퀵 정렬

이 "가르는" 일을 하는 게 partition입니다. 맨 끝 원소를 피벗으로 삼고, 피벗보다 작은 값들을 왼쪽으로 당겨 모은 뒤 피벗을 그 경계로 옮겨요.

def quick_sort(arr):
    a = list(arr)
    _quick_sort(a, 0, len(a) - 1)
    return a


def _quick_sort(a, lo, hi):
    if lo < hi:
        p = partition(a, lo, hi)           # 피벗을 제자리에 놓고 그 위치를 받는다
        _quick_sort(a, lo, p - 1)          # 피벗 왼쪽(작은 값들)
        _quick_sort(a, p + 1, hi)          # 피벗 오른쪽(큰 값들)


def partition(a, lo, hi):
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]       # 피벗을 작은/큰 무리의 경계로 옮긴다
    return i + 1

i는 "피벗보다 작은 값들의 마지막 위치"를 가리킵니다. j로 훑다가 피벗 이하인 값을 만나면 i를 한 칸 늘려 그 자리로 당겨 와요. 다 훑으면 피벗을 i+1로 보내 작은 무리와 큰 무리의 경계에 놓습니다.

퀵 정렬의 시간 복잡도는 두 얼굴입니다. 피벗이 매번 딱 중간값이면 병합 정렬처럼 반씩 쪼개져 평균 O(n log n)이에요. 그런데 피벗이 매번 한쪽 끝값이면(예를 들어 이미 정렬된 입력에 맨 끝을 피벗으로 잡으면) 분할이 1과 나머지로 치우쳐 O(n²)로 무너집니다. 이게 퀵 정렬의 유명한 최악의 경우예요. 추가 공간은 재귀 호출 스택으로 평균 O(log n)입니다.

병합과 퀵을 나란히 두면 성격이 잘 드러납니다.

🎯 코테에서는 퀵 정렬을 직접 짜기보다, "왜 최악이 O(n²)인가"와 "어떻게 피하나(피벗을 무작위나 중앙값으로)"를 면접에서 자주 묻습니다. 파이썬 내장 정렬은 퀵이 아니라 병합 계열(Timsort)이라 이 최악을 피한다는 점도 함께 기억해 두세요.

💡 한 줄 정리

퀵 정렬은 피벗으로 좌우를 갈라 제자리에서 정렬하는 분할정복으로, 평균 O(n log n)이지만 피벗이 치우치면 최악 O(n²)가 된다.

Step 5: "다 넣고 하나씩 빼면? — 힙 정렬과 O(n log n) 삼총사"

O(n log n) 정렬이 하나 더 있습니다. 그런데 이건 새로 배우는 게 아니라, 지난 시간에 이미 절반을 만들어 뒀어요. C-2에서 힙을 배우며 이런 말을 했던 걸 기억하시나요? "최소 힙은 가장 작은 값이 늘 맨 위에 있으니, 전부 넣고 하나씩 빼면 작은 순서대로 나온다." 그게 바로 힙 정렬(heap sort)입니다.

원리를 다시 짚으면, 최소 힙은 넣을 때(push)나 뺄 때(pop)나 트리 높이만큼만 손보면 되니 O(log n)이었죠. 그러니 n개를 다 넣고 하나씩 빼면 오름차순으로 정렬돼서 나옵니다. 여기서는 C-2에서 직접 짠 MinHeap 대신, 실전에서 쓰는 표준 라이브러리 heapq를 그대로 씁니다.

def heap_sort(arr):
    import heapq
    a = list(arr)
    heapq.heapify(a)                        # 리스트를 최소 힙으로 O(n)
    return [heapq.heappop(a) for _ in range(len(a))]   # 하나씩 빼면 오름차순 O(n log n)

heapify는 리스트를 통째로 최소 힙으로 만드는데 O(n)이고, 그 뒤 heappop을 n번 하면 각 pop이 O(log n)이라 전체가 O(n log n)입니다. 힙은 완전 이진트리라 높이가 늘 log n으로 균형이 보장돼요. 그래서 퀵 정렬과 달리 최악에도 O(n log n)이 무너지지 않습니다. 다만 정렬 결과를 담을 새 리스트가 필요해 공간은 O(n)이고, 힙에 넣고 빼는 과정에서 같은 값의 순서가 흐트러질 수 있어 불안정합니다.

이제 O(n log n) 세 정렬이 다 모였습니다. 병합·퀵·힙을 세 잣대로 견줘 보면 각자 언제 빛나는지 보여요.

세 정렬 다 O(n log n)이지만 결이 다릅니다. 병합은 안정적이고 최악이 없지만 메모리를 더 쓰고, 퀵은 평균 최고속이지만 최악이 있고, 힙은 최악이 없지만 불안정합니다. "공짜 점심은 없다"는 말이 여기서도 통해요.

🎯 코테에서는 힙 정렬을 통째로 쓰기보다, 힙의 "가장 급한 것부터 꺼낸다"는 성질을 K번째 큰 수, 우선순위 큐, 다익스트라(F-1) 같은 데서 씁니다. "전체를 정렬할 필요 없이 상위 K개만" 필요할 때 힙이 특히 강해요(전부 정렬하는 O(n log n) 대신 O(n log K)).

💡 한 줄 정리

힙 정렬은 C-2의 힙으로 "다 넣고 하나씩 빼면 정렬"을 실현하며, 병합·퀵·힙 세 O(n log n) 정렬은 안정성·공간·최악 보장에서 서로 다르게 절충한다.

Step 6: "빅오로 고르는 정렬 — 입력 크기별 판단"

정렬을 여섯 개 배웠으니, 이제 "언제 무엇을 쓰나"를 정리할 차례입니다. 코딩테스트의 첫 판단은 늘 똑같아요. 입력 크기 n을 보고 "어떤 복잡도까지 시간 안에 드나"를 가늠하는 거죠. A-1에서 배운 "1초에 약 1억 번 연산" 잣대를 정렬에 대 봅시다.

표가 말해 주는 게 분명합니다. n이 수만을 넘어가면 O(n²) 정렬은 시간 초과예요. n=100,000만 돼도 O(n²)는 100억 번이라 100초쯤 걸리는데, O(n log n)은 170만 번이라 눈 깜짝할 새죠. 그래서 코테에서 "정렬해야겠다" 싶으면 거의 항상 O(n log n)을 씁니다.

그럼 O(n²) 정렬은 배울 필요도 없었을까요? 그렇진 않습니다. 두 가지 경우가 있어요. 첫째, 입력이 아주 작을 때(수십 개)는 O(n²)든 O(n log n)이든 차이가 없고, 오히려 간단한 삽입 정렬이 상수가 작아 더 빠를 수도 있습니다. 둘째, 거의 정렬된 데이터라면 삽입 정렬이 O(n)까지 빨라져 O(n log n)보다도 유리해요. 실제로 파이썬 내장 정렬이 이 성질을 씁니다(다음 Step에서 봅니다).

정리하면 이렇게 고릅니다.

 정렬 고르는 눈 — 흐름으로 보기

  입력이 수십 개로 아주 작다        →  아무거나 (삽입이 간단·빠름)
  거의 정렬돼 있다                 →  삽입 정렬 (O(n)에 근접)
  일반적인 큰 입력                 →  O(n log n) (실전은 내장 정렬)
   ├ 안정성이 필요하다            →  병합 (또는 내장 정렬)
   ├ 메모리가 빠듯하다            →  퀵 (제자리)
   └ 상위 K개만 필요하다          →  힙

🎯 코테에서는 문제를 받으면 제일 먼저 입력 크기 제한(n의 범위)을 봅니다. n이 100만이면 O(n²)는 애초에 후보에서 빠지고, "정렬 후 O(n) 또는 O(log n)으로 푸는" 방향을 잡아야 해요. 입력 크기가 알고리즘을 고르는 나침반입니다.

💡 한 줄 정리

n이 수만을 넘으면 O(n²) 정렬은 시간 초과라 O(n log n)을 쓰되, 아주 작거나 거의 정렬된 입력에서는 삽입 정렬이 오히려 유리하다.

Step 7: "실전에선 결국 내장 정렬 — 그리고 비교의 벽"

오늘 여섯 정렬을 손으로 짜 봤습니다. 그런데 솔직히 말하면, 실전 코딩테스트에서 이걸 직접 짜는 일은 거의 없습니다. 파이썬이 이미 훌륭한 정렬을 내장하고 있거든요.

sorted([5, 2, 9, 1, 5, 6])        # → [1, 2, 5, 5, 6, 9] (새 리스트 반환)
nums.sort()                        # 리스트를 제자리에서 정렬 (반환값 None)

sorted()와 list.sort()는 C로 구현돼 있어 우리가 파이썬으로 짠 것보다 훨씬 빠르고, 오랜 세월 검증돼 버그도 없습니다. 그래서 두 트랙으로 기억하세요. 원리는 오늘처럼 직접 짜서 이해하고, 실전에선 내장 정렬을 씁니다. 직접 짜는 건 면접에서 원리를 묻거나, 표준에 없는 특별한 변형이 필요할 때예요.

파이썬 내장 정렬의 정체가 재밌습니다. Timsort라는 정렬인데, 오늘 배운 병합 정렬과 삽입 정렬을 섞은 하이브리드예요. 큰 흐름은 병합 정렬로 O(n log n)을 보장하되, 작은 조각이나 이미 정렬된 부분은 삽입 정렬로 빠르게 처리합니다. Step 2에서 "삽입 정렬은 Timsort의 부품"이라 했던 게 이 대목이에요. 그리고 Timsort는 안정 정렬이라, 파이썬 sorted()는 늘 안정적입니다.

정렬로 무엇을 커스텀할 수 있는지(정렬 기준을 바꾸는 key, 튜플로 여러 기준을 한 번에 거는 법)는 다음 시간에 본격적으로 다룹니다. 오늘은 "실전은 내장 정렬"이라는 큰 그림만 잡아 두세요.

마지막으로 한 가지 벽을 짚고 넘어갑니다. 오늘 배운 정렬은 전부 원소끼리 비교했죠. 그런데 비교만으로 정렬하면 아무리 잘해도 O(n log n)이 한계입니다. 이걸 비교 정렬의 하한이라고 불러요. 그렇다면 이 벽을 넘을 방법은 없을까요? 있습니다. 비교를 아예 하지 않으면 됩니다. 값을 세거나 자릿수로 나누면 비교 없이 O(n)에 정렬할 수 있어요. 그게 다음 시간의 주인공, 계수 정렬과 기수 정렬입니다.

🎯 코테에서는 정렬은 sorted() 한 줄로 끝내는 게 정석입니다. 시간을 아껴 진짜 문제(정렬 후의 로직)에 집중하세요. 다만 "정렬이 안정적인가"를 물으면 파이썬은 안정 정렬이라고 답할 수 있어야 하고, 커스텀 정렬 기준(key)은 다음 시간에 확실히 익힙니다.

💡 한 줄 정리

실전에선 C로 구현된 안정 정렬 Timsort(sorted/list.sort)를 쓰며, 비교 정렬의 한계인 O(n log n)을 넘으려면 비교를 버린 계수·기수 정렬(다음 시간)이 필요하다.

마무리

오늘은 카테고리 D의 문을 열며 비교 기반 정렬 여섯 가지를 손으로 짰습니다. 뒤죽박죽인 데이터를 O(n²)의 소박한 방법으로 줄 세워 보고, 분할정복으로 O(n log n)까지 끌어내린 뒤, 세 잣대로 골라 쓰는 눈까지 길렀어요.

오늘 배운 핵심 세 가지

• 💡 하나 — 소박한 정렬 셋은 모두 O(n²)다. 버블·선택·삽입은 비교하고 자리를 바꾸는 발상이지만 O(n²)라 큰 입력엔 느리다. 단 삽입 정렬은 거의 정렬된 입력에서 O(n)으로 빨라지고 안정적이다.
• 💡 둘 — 분할정복으로 O(n log n)까지 내려간다. 병합 정렬은 반씩 쪼개 합쳐 최악에도 O(n log n)을 보장하고, 퀵 정렬은 피벗으로 갈라 평균 O(n log n)이지만 치우치면 최악 O(n²)가 된다.
• 💡 셋 — 힙 정렬로 C-2를 회수하고, 세 잣대로 고른다. "다 넣고 하나씩 빼면 정렬"이 힙 정렬이다. 병합·퀵·힙 세 O(n log n) 정렬은 안정성·공간·최악 보장에서 다르게 절충하니, 입력 크기와 요구를 보고 고른다.

다음 시간 예고

오늘 마지막에 "비교만으로는 O(n log n)이 한계"라는 벽을 만났습니다. 다음 시간(D-2)엔 그 벽을 넘습니다. 비교를 아예 하지 않고 값을 세어 O(n)에 정렬하는 계수 정렬과, 자릿수로 나눠 정렬하는 기수 정렬을 배워요. 그리고 오늘 잠깐 스친 실전 내장 정렬을 제대로 다룹니다. 정렬 기준을 바꾸는 key, 튜플로 여러 기준을 한 번에 거는 법, 그리고 "언제 직접 짜고 언제 내장을 쓰나"의 판단까지. 오늘 짠 여섯 정렬이 그 판단의 바탕이 됩니다.

과제

오늘 배운 여섯 정렬과 빅오 감각을 다지는 문제들입니다. 코드베이스 algorithms/sorting.py의 함수들을 그대로 쓰거나, 직접 변형해 풀어 보세요.

[기초] K번째로 작은 수 찾기

정수 리스트 nums와 정수 k가 주어질 때, nums에서 k번째로 작은 값을 반환하는 kth_smallest(nums, k)를 작성하세요(k는 1부터 시작). 예를 들어 kth_smallest([5, 2, 9, 1, 6], 2)는 두 번째로 작은 값인 2를 반환합니다.

• 정렬을 이용하면 아주 간단해집니다. "정렬해 두면 순위 문제가 쉬워진다"를 몸으로 느껴 보세요.
• 시간·공간 복잡도를 빅오로 적고, 왜 그런지 한 줄로 설명하세요.

[응용] 퀵 정렬의 최악을 피하기 (중앙값 피벗)

Step 4에서 본 퀵 정렬은 이미 정렬된 입력에서 최악 O(n²)로 무너졌습니다. 피벗을 맨 끝값 대신 "처음·중간·끝 세 값의 중앙값"으로 고르도록 partition을 손봐, 이미 정렬된 입력에서도 치우치지 않게 만드세요(median-of-three).

• 이미 정렬된 list(range(1000)) 같은 입력에서, 원래 퀵 정렬과 개선한 퀵 정렬이 재귀 깊이가 어떻게 달라지는지 생각해 보세요.
• 중앙값을 피벗으로 옮긴 뒤에는 기존 partition 로직을 그대로 쓸 수 있습니다.

[심화] 역순 쌍(inversion) 개수 세기

리스트에서 i < j인데 nums[i] > nums[j]인 쌍을 역순 쌍이라 합니다. "얼마나 뒤섞여 있나"를 나타내는 값이에요. [3, 1, 2]에는 (3,1), (3,2) 두 개의 역순 쌍이 있습니다. 역순 쌍의 개수를 O(n log n)에 세는 count_inversions(nums)를 작성하세요.

• 하나하나 다 세면 O(n²)입니다. 병합 정렬의 merge 단계를 활용하면 O(n log n)에 셀 수 있어요. 오른쪽 조각의 값이 왼쪽 조각의 값보다 먼저 담길 때, 그 값보다 뒤에 남은 왼쪽 원소들이 전부 역순 쌍입니다.
• 병합 정렬을 회수하는 대표적인 코테 심화 유형입니다.

생각해볼 주제

1. 버블·선택·삽입 다 O(n²)인데, 왜 셋을 다 배울까?

세 정렬 모두 O(n²)라 실전에선 큰 입력에 못 씁니다. 그런데도 교과서가 셋을 다 다루는 이유가 있어요. 특히 삽입 정렬은 다른 둘과 다른 강점이 있습니다. 셋의 차이가 어디서 오는지, 삽입 정렬만의 강점(거의 정렬된 입력·안정성·데이터가 실시간으로 들어오는 상황)이 실무에서 왜 쓸모 있는지 정리해 보세요.

2. 퀵 정렬은 왜 최악이 O(n²)인데도 실무 표준일까?

병합·힙은 최악에도 O(n log n)인데, 퀵은 최악이 O(n²)입니다. 그런데도 오랫동안 많은 언어의 기본 정렬이 퀵 계열이었어요. 왜 "최악이 더 나쁜" 정렬이 실무에서 사랑받았을까요? 평균 성능과 최악 성능 중 무엇을 봐야 하는지, 그리고 최악을 어떻게 낮추는지(피벗 무작위화·중앙값)를 함께 생각해 보세요.

3. 같은 O(n log n)인데 병합·퀵·힙을 무엇으로 고를까?

셋 다 O(n log n)이라 빅오만으로는 우열을 못 가립니다. 안정성이 필요한 상황, 메모리가 빠듯한 상황, 최악의 시간을 반드시 보장해야 하는 상황을 각각 떠올리고, 그때 셋 중 무엇을 고를지 근거를 세워 보세요. "빅오가 같아도 세부 성질로 고른다"는 감각이 목표입니다.