C++ sort 정리: 람다, 오름차순, 내림차순

기본 사용

#include <algorithm>
#include <vector>

vector<int> v = {3, 1, 4, 1, 5};
sort(v.begin(), v.end());  // {1, 1, 3, 4, 5} — 기본 오름차순

sort는 기본적으로 operator<를 사용한다. 즉 오름차순이다
Random Access Iterator가 필요하다. vector, deque, array, C 배열에서 사용 가능하다
list, set 등에서는 사용할 수 없다. list는 멤버 함수 l.sort()를 쓴다

오름차순 / 내림차순

// 오름차순 (기본)
sort(v.begin(), v.end());               // operator< 사용
sort(v.begin(), v.end(), less<int>());   // 명시적으로 동일

// 내림차순
sort(v.begin(), v.end(), greater<int>()); // operator> 사용
sort(v.begin(), v.end(), greater<>());    // C++14 투명 비교자

less<>와 greater<>는 C++14부터 사용 가능한 투명 비교자다. 타입을 명시하지 않아도 된다
less<int>()는 a < b가 true면 a를 앞에 놓는다
greater<int>()는 a > b가 true면 a를 앞에 놓는다

람다로 커스텀 정렬

람다 기본 문법

[캡처](매개변수) -> 반환타입 { 본문 }

캡처: 외부 변수를 람다 안에서 사용할 때. []이면 캡처 없음
매개변수: 함수 매개변수와 동일
-> 반환타입: 생략 가능. 컴파일러가 추론한다
본문: 실행할 코드

정렬에서의 람다

// 절댓값 기준 오름차순
sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);
});

// 문자열 길이 기준 내림차순
vector<string> words = {"hi", "hello", "a"};
sort(words.begin(), words.end(), [](const string& a, const string& b) {
    return a.size() > b.size();
});

비교 함수는 a가 b보다 앞에 와야 하면 true를 반환한다.

return a < b; → 오름차순
return a > b; → 내림차순

캡처

int threshold = 10;

// 값 캡처: 복사본을 가져온다
sort(v.begin(), v.end(), [threshold](int a, int b) {
    return abs(a - threshold) < abs(b - threshold);
});

// 참조 캡처: 원본을 참조한다
sort(v.begin(), v.end(), [&threshold](int a, int b) {
    return abs(a - threshold) < abs(b - threshold);
});

// 전체 캡처
[=]  // 모든 외부 변수를 값으로 캡처
[&]  // 모든 외부 변수를 참조로 캡처

정렬 비교 함수에서는 [=]와 [&] 차이가 거의 없다. 정렬 도중에 외부 변수가 바뀔 일이 없기 때문이다
int 같은 기본 타입은 값 캡처가 낫다. vector나 string은 참조 캡처가 낫다

다중 기준 정렬

struct Student {
    string name;
    int score;
};

vector<Student> students;

// 점수 내림차순 → 같으면 이름 오름차순
sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    if (a.score != b.score)
        return a.score > b.score;
    return a.name < b.name;
});

pair/tuple의 기본 비교를 활용하면 간결하게 쓸 수 있다.

// pair: first 기준 → first 같으면 second 기준 (둘 다 오름차순)
vector<pair<int,int>> vp;
sort(vp.begin(), vp.end());  // {first 오름, second 오름}

// first 오름차순, second 내림차순이 필요하면 람다를 쓴다
sort(vp.begin(), vp.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
    if (a.first != b.first)
        return a.first < b.first;
    return a.second > b.second;
});

stable_sort

stable_sort(v.begin(), v.end());

같은 값의 원래 순서를 보장한다
sort는 보장하지 않는다 (introsort, 불안정 정렬)
다중 기준 정렬에서 한 기준씩 순차적으로 정렬할 때 유용하다

partial_sort / nth_element

// 상위 3개만 정렬
partial_sort(v.begin(), v.begin() + 3, v.end());
// v[0], v[1], v[2]는 정렬됨. 나머지는 미정

// k번째 원소만 올바른 위치에 놓기
nth_element(v.begin(), v.begin() + k, v.end());
// v[k]는 정렬했을 때와 같은 값. 나머지 순서는 미정

함수	시간	용도
`sort`	O(N log N)	전체 정렬
`stable_sort`	O(N log N), 메모리 O(N)	안정 정렬
`partial_sort`	O(N log K)	상위 K개만 필요할 때
`nth_element`	O(N) 평균	K번째 원소만 필요할 때

비교 함수 주의사항

비교 함수는 strict weak ordering을 만족해야 한다.

// 잘못된 예: a == b일 때 true를 반환
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;  // 미정의 동작!
});

// 올바른 예
sort(v.begin(), v.end(), [](int a, int b) {
    return a < b;
});

a == b이면 반드시 false를 반환해야 한다
<=, >=를 쓰면 안 된다. 무한 루프나 크래시가 발생할 수 있다