정렬 알고리즘

버블·선택·삽입부터 병합·퀵까지 — 원리와 복잡도.

실버 V

1강 정렬의 원리와 복잡도 공식

왜 정렬을 배우는가

내장 sort를 쓰는 법은 이미 익혔습니다. 이번에는 그 내부가 어떻게 동작하는지
들여다봅니다. 정렬 알고리즘의 원리를 이해하면 복잡도 감각이 단단해지고, 안정
정렬·부분 정렬 같은 변형 상황에서 올바른 선택을 할 수 있습니다.

정렬은 비교 기반이라면 이론적으로 $O(N \log N)$ 보다 빠를 수 없다는 하한이
있습니다. 그 한계에 도달하는 대표 알고리즘이 병합 정렬과 퀵 정렬입니다.

1. $$O(N^2)$$ 정렬들 — 단순하지만 느림

선택 정렬: 남은 부분에서 최솟값을 골라 맨 앞과 바꿉니다.

for (int i = 0; i < n; i++) {
    int m = i;
    for (int j = i + 1; j < n; j++)
        if (a[j] < a[m]) m = j;
    swap(a[i], a[m]);
}

삽입 정렬: 카드를 손에 정렬해 들 듯, 앞쪽 정렬된 부분에 하나씩 끼워 넣습니다.
이미 거의 정렬된 데이터에서는 $$O(N)$$ 에 가깝게 빨라지는 장점이 있습니다.

for (int i = 1; i < n; i++) {
    int key = a[i], j = i - 1;
    while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
    a[j + 1] = key;
}

이들은 모두 $$O(N^2)$$ 라 $N \le 1000$ 정도까지만 실용적입니다.

2. 병합 정렬 — 분할 정복의 정석

배열을 반으로 쪼개 각각 정렬한 뒤, 정렬된 두 줄을 한 줄로 합치는(merge)
방식입니다. 합치는 데 $$O(N)$$ , 쪼개는 깊이가 $\log N$ 이므로 전체 $O(N \log N)$ .

병합 정렬의 두 가지 큰 장점:

안정 정렬(stable) — 값이 같으면 원래 순서를 유지합니다.
최악에도 보장된 $O(N \log N)$ — 입력 모양에 흔들리지 않습니다.

분할 정복으로 합치는 과정에서 "왼쪽 원소보다 작은 오른쪽 원소의 개수"를 세면
역순쌍(inversion) 카운팅도 공짜로 됩니다.

3. 퀵 정렬 — 평균적으로 가장 빠름

피벗(pivot) 을 하나 골라 그보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 분할한 뒤
양쪽을 재귀적으로 정렬합니다. 평균 $O(N \log N)$ 이며 상수가 작아 실측이 빠릅니다.

다만 피벗을 운 나쁘게 고르면(이미 정렬된 배열에서 끝값을 피벗으로) 최악
$$O(N^2)$$ 로 떨어집니다. 그래서 라이브러리는 무작위 피벗이나 중앙값 전략을 씁니다.

4. 비교: 무엇을 언제 쓰나

알고리즘	평균	최악	안정성	비고
선택/삽입	$$O(N^2)$$	$$O(N^2)$$	삽입은 안정	작은 N
병합	$O(N \log N)$	$O(N \log N)$	안정	추가 메모리 $$O(N)$$
퀵	$O(N \log N)$	$$O(N^2)$$	불안정	제자리, 빠름

실전에서는 거의 항상 내장 sort(보통 퀵+힙+삽입 혼합인 introsort)나
stable_sort(병합 기반)를 씁니다. 원리를 아는 이유는 직접 짜기 위해서가 아니라,
복잡도와 안정성을 정확히 판단하기 위해서입니다.

정리

비교 정렬의 하한은 $O(N \log N)$ 입니다. 단순 정렬은 작은 $$N$$ 에서만, 큰 $$N$$ 에서는
$N \log N$ 정렬을 씁니다. 안정성이 필요하면 병합 계열을 떠올리세요.

2강 병합·퀵 정렬 구현과 안정 정렬 공식

직접 짜 보며 이해하기

원리를 이해했다면 한 번쯤 손으로 짜 보는 것이 가장 확실합니다. 여기서는 병합
정렬과 퀵 정렬을 C++/Python으로 구현하고, 실전에서 마주치는 안정 정렬 이슈를
다룹니다.

1. 병합 정렬 구현

int tmp[100001];
void mergeSort(int* a, int l, int r) {
    if (l >= r) return;
    int m = (l + r) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m + 1, r);
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r)          // 두 줄을 비교하며 합친다
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= m) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int t = l; t <= r; t++) a[t] = tmp[t];
}

def merge_sort(a):
    if len(a) <= 1:
        return a
    m = len(a) // 2
    left, right = merge_sort(a[:m]), merge_sort(a[m:])
    res, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:       # <=라야 안정 정렬
            res.append(left[i]); i += 1
        else:
            res.append(right[j]); j += 1
    res.extend(left[i:]); res.extend(right[j:])
    return res

비교에서 a[i] <= a[j]처럼 왼쪽을 먼저 가져가게 해야 같은 값에서 원래
순서가 유지되어 안정 정렬이 됩니다.

2. 퀵 정렬 구현

void quickSort(int* a, int l, int r) {
    if (l >= r) return;
    int pivot = a[(l + r) / 2], i = l, j = r;
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) swap(a[i++], a[j--]);
    }
    quickSort(a, l, j);
    quickSort(a, i, r);
}

피벗을 가운데서 고르면 이미 정렬된 입력에서의 최악 $$O(N^2)$$ 를 어느 정도
피할 수 있습니다.

3. 안정 정렬이 필요한 순간

여러 기준으로 정렬해야 할 때(예: 나이 오름차순, 같으면 입력 순서 유지)
안정성이 중요합니다.

stable_sort(v.begin(), v.end(),
            [](auto& a, auto& b){ return a.age < b.age; });

파이썬의 sort/sorted는 항상 안정(Timsort)이므로, 여러 기준은 덜
중요한 기준부터 차례로 정렬하면 됩니다.

people.sort(key=lambda p: p.name)   # 2순위 먼저
people.sort(key=lambda p: p.age)    # 1순위 나중 (안정이라 name 순서 유지)

물론 한 번에 튜플 키로 정렬하는 게 더 깔끔합니다: key=lambda p: (p.age, p.name).

4. 흔한 실수와 점검

불안정 정렬에 안정성을 기대 — std::sort는 불안정합니다. 같은 값의 순서를
보장하려면 stable_sort를 쓰거나 키에 인덱스를 함께 넣으세요.
재귀 종료 조건 누락 — l >= r에서 멈춰야 무한 재귀를 피합니다.
추가 배열 크기 — 병합 정렬의 tmp를 함수 안에서 매번 새로 잡으면 느립니다.
전역으로 한 번만 잡으세요.

5. 패턴 알아보기

"역순쌍의 개수를 구하라" → 병합 정렬 변형.
"여러 우선순위로 정렬" → 안정 정렬 또는 튜플 키.
실전 경쟁에서 정렬이 필요하면 직접 짜지 말고 내장 정렬을 쓰되, 복잡도와
안정성은 이 강의 지식으로 판단하세요.

3강 실전 가이드 — 정렬이 풀이의 첫 줄이 되는 순간 공식

실전에서 정렬 문제 알아보기

정렬 자체를 묻는 문제는 드뭅니다. 실전에서는 정렬이 풀이의 전처리로
쓰이는 경우가 압도적으로 많고, 그 신호를 읽는 것이 핵심입니다.

1. 출제 신호

" $$k$$ 번째 수", "중앙값", "상위 $$m$$ 개" — 순서 통계는 정렬 한 번이면 끝.
"가장 가까운 두 수", "차이의 최솟값" — 정렬하면 답 후보가 이웃끼리로
줄어듭니다.
처리 순서가 답에 영향을 주지 않는다 — 입력 순서를 마음대로 바꿔도 되면
유리한 순서로 재배열할 수 있다는 뜻입니다.
좌표·시각·구간이 등장하고 "겹침/순서" 를 따집니다 — 거의 항상 정렬 후
한 번 훑기(스위프)입니다.
정렬은 이분 탐색·투 포인터·그리디의 선행 조건입니다. 그 기법들이 보이면
정렬부터 의심하세요.

2. 풀이 결정 절차

무엇을 키로 정렬할까? — 값, 끝나는 시간, (나이, 입력 순서)처럼 복합 키.
동률 처리를 정합니다 — 같은 키일 때 무엇이 먼저여야 하는가?
안정성이 필요한가? — 입력 순서를 보존해야 하면 C++은 stable_sort,
파이썬 sort는 항상 안정 정렬입니다.
정렬 후 무엇을 할지 정합니다 — 이웃 비교, 이분 탐색, 투 포인터, 그리디 선택.

3. 자주 하는 실수

비교 함수에 <=를 사용. C++ 비교자는 strict weak ordering이어야
합니다. 같을 때 true를 돌려주면 정의되지 않은 동작(런타임 에러)입니다.

// 나쁨: return a.x <= b.x;   ← 같을 때 true → UB
bool cmp(const P& a, const P& b) {
    if (a.x != b.x) return a.x < b.x;   // 1차 키
    return a.y < b.y;                   // 동률이면 2차 키
}

원래 인덱스를 잃어버림. "정렬 후 원래 몇 번째였는지"가 필요하면
값과 인덱스를 묶어 (값, 인덱스) 쌍으로 정렬하세요.
뺄셈 비교자 오버플로. return a - b; 식의 C 스타일 비교는 큰 음수/양수에서
오버플로합니다. 항상 < 비교를 쓰세요.
문자열 수 비교. "10" < "9"는 사전순으로 참입니다. 수치 비교가 필요하면
변환하거나, 자릿수를 1차 키로 두세요.
느린 정렬 직접 구현. $N \le 10^5$ 이상에서 버블/삽입 정렬( $$O(N^2)$$ )은
시간 초과입니다. 라이브러리 정렬( $O(N \log N)$ )이 기본값입니다.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 순 → 어려운 순으로 정렬되어 있습니다.
앞쪽에서 단일 키 정렬을, 뒤로 가며 복합 키·안정 정렬·정렬 후 스위프 문제를
만나도록 구성되어 있으니 순서대로 푸는 것을 권합니다.

문제를 풀 때마다 "이 문제의 정렬 키는 무엇이고 동률 처리 규칙은 무엇인가"를
한 줄로 적고 시작해 보세요. 3문제 이상 해결해 알고리즘을 클리어하면
레이팅의 CLASS 보너스에 반영됩니다.