내장 정렬 사용하기

정렬을 직접 짜지 말자

데이터를 크기순으로 줄 세우는 일은 너무 흔해서, 모든 언어가 빠른 정렬 함수를
기본 제공합니다. 직접 짠 정렬보다 빠르고 정확하니, 정렬이 필요하면 내장 함수를
쓰는 게 정답입니다.

1. 기본 정렬 (오름차순)

#include <algorithm>
int a[5] = {3, 1, 4, 1, 5};
sort(a, a + 5);             // 배열: 시작, 끝 다음
// vector면: sort(v.begin(), v.end());

a = [3, 1, 4, 1, 5]
a.sort()             # 원본을 정렬
b = sorted(a)        # 정렬된 새 리스트 반환

C++ sort는 평균 \(O(N \log N)\)으로 매우 빠릅니다. 직접 짠 \(O(N^2)\) 정렬과는
비교가 안 됩니다.

2. 내림차순

sort(a, a + 5, greater<int>());   // 큰 것부터

a.sort(reverse=True)

3. 기준을 직접 정하기 (비교 함수)

"키 순, 같으면 이름 순"처럼 정렬 기준을 직접 정할 수 있습니다.

struct Person { int height; string name; };
bool cmp(const Person& a, const Person& b) {
    if (a.height != b.height) return a.height < b.height;  // 키 오름차순
    return a.name < b.name;                                // 같으면 이름순
}
sort(people, people + n, cmp);

people.sort(key=lambda p: (p[0], p[1]))   # 첫째 기준, 같으면 둘째

비교 함수는 "a가 b보다 앞에 와야 하면 true" 를 돌려주도록 짭니다. 파이썬은
key에 "정렬에 쓸 값"을 주면 알아서 비교합니다(튜플로 우선순위 표현).

4. 정렬이 푸는 문제들

• 중앙값·최댓값·k번째 값 찾기.
• "가장 적게/많이"류 그리디.
• 정렬해 두면 이분 탐색이 가능.
• 같은 값 묶기(정렬 후 인접 비교).

복잡도

내장 정렬은 \(O(N \log N)\)입니다. \(N = 10^6\)이어도 약 \(2 \times 10^7\) 수준이라
충분히 빠릅니다.

정리

• 정렬은 직접 짜지 말고 내장 함수(sort / .sort()).
• 오름차순 기본, 내림차순은 greater/reverse=True.
• 기준은 비교 함수(C++) / key(파이썬)로 자유롭게.
• 복잡도 \(O(N \log N)\) — 빠르고 안전.

내장 정렬 구현 레퍼런스

자주 쓰는 정렬 패턴 — 다중 기준, 구조체/튜플 정렬, 정렬 후 처리 — 을 코드로
정리하고 함정을 짚습니다.

1. 수 정렬 후 통계

int n; cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x;
sort(a.begin(), a.end());
cout << a[0] << ' ' << a[n-1] << ' ' << a[n/2] << '\n';  // 최소, 최대, 중앙값

n = int(input())
a = sorted(map(int, input().split()))
print(a[0], a[-1], a[n // 2])

정렬해 두면 최소(맨 앞), 최대(맨 뒤), 중앙값(가운데)을 즉시 꺼낼 수 있습니다.

2. 다중 기준 정렬 (좌표 등)

"x 오름차순, x가 같으면 y 오름차순":

vector<pair<int,int>> pts(n);
for (auto& p : pts) cin >> p.first >> p.second;
sort(pts.begin(), pts.end());   // pair는 first, second 순으로 자동 비교

pts = [tuple(map(int, input().split())) for _ in range(n)]
pts.sort()           # 튜플은 앞 원소부터 차례로 비교

C++ pair/tuple과 파이썬 튜플은 앞 원소부터 차례로 비교되므로, 우선순위
순서대로 묶기만 하면 다중 기준이 공짜로 됩니다.

3. 커스텀 비교 함수

// 절댓값 오름차순, 절댓값 같으면 원래 값 오름차순
sort(a.begin(), a.end(), [](int x, int y){
    if (abs(x) != abs(y)) return abs(x) < abs(y);
    return x < y;
});

a.sort(key=lambda x: (abs(x), x))

람다(이름 없는 함수)로 그 자리에서 기준을 정의할 수 있습니다.

4. 정렬 후 인접 처리 (중복 제거 등)

sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());  // 중복 제거

a = sorted(set(a))    # 정렬 + 중복 제거

5. 함정과 패턴 인식

• 비교 함수 규칙 — C++ cmp는 같을 때 false를 줘야 함(<= 쓰면 런타임 에러).
• sort 범위 — 배열은 sort(a, a+n), 벡터는 v.begin(), v.end().
• 원본 보존 — 정렬하면 원래 순서가 사라짐. 필요하면 인덱스를 함께 저장.
• 안정 정렬 필요 시 — 같은 값의 순서 유지가 중요하면 stable_sort.

문제에 "정렬하라", "k번째 작은 수", "키 순으로", "오름/내림차순", "중앙값"
같은 말이 보이면 내장 정렬을 떠올리세요.

정리

내장 정렬 활용의 핵심은 (1) sort/.sort()로 \(O(N \log N)\) 정렬, (2) 다중 기준은
pair/tuple 또는 key로, (3) 커스텀은 비교 함수(a<b이면 앞으로), (4) 정렬 후
인접 비교로 중복·묶기 처리입니다.