[내배캠 TIL 260224] C++ std::sort 커스텀 비교 함수 구현하기

1. std::sort 기본 개념

1) 기본 동작

std::sort는 <algorithm>에 정의되어 있으며 기본적으로 a < b 기준의 오름차순 정렬을 수행한다.

sort(vec.begin(), vec.end());

내부적으로 operator<를 사용한다.

---

2) 커스텀 비교 함수 (Comparator)

세 번째 인자로 비교 함수를 전달하면 원하는 기준으로 정렬할 수 있다.

sort(begin, end, comparator);

 

Comparator 규칙

• 반환 타입: bool
• 매개변수: 보통 const T&
• 의미: 첫 번째 인자가 두 번째 인자보다 앞에 와야 하면 true 반환
• Strict Weak Ordering을 만족해야 함

---

2. 기본 구현 방식 (전역 변수 사용)

정렬 기준이 되는 인덱스를 전역 변수로 두고 비교 함수에서 참조하는 방식.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int target_idx;

bool compare(const string& a, const string& b) {
    if (a[target_idx] != b[target_idx]) {
        return a[target_idx] < b[target_idx];
    }
    return a < b;
}

vector<string> solution(vector<string> strings, int n) {
    target_idx = n;
    sort(strings.begin(), strings.end(), compare);
    return strings;
}

주의할 점

• 전역 변수명으로 index 같은 일반적인 이름을 사용하면 환경에 따라 충돌이 발생할 수 있다.
• 가능하면 전역 변수 사용을 피하는 것이 좋다.

---

3. 더 나은 구현 방식

1) 람다식 사용

전역 변수 없이 sort 호출부에서 직접 정의하는 방식.

sort(strings.begin(), strings.end(),
     [n](const string& a, const string& b) {
         if (a[n] != b[n]) return a[n] < b[n];
         return a < b;
     });

장점

• 전역 변수 제거
• 정렬 기준이 한눈에 보임
• 현대 C++ 스타일에 적합

---

2) std::tie 활용

여러 조건을 한 번에 비교할 수 있다.

#include <tuple>

sort(strings.begin(), strings.end(),
     [n](const string& a, const string& b) {
         return tie(a[n], a) < tie(b[n], b);
     });

tie(a[n], a)는 (1순위 기준, 2순위 기준)을 하나의 튜플로 묶어 사전식 비교를 수행한다.

if-else 없이 우선순위 정렬을 표현할 수 있어 가독성이 좋다.

---

4. 정리

1. std::sort는 세 번째 인자로 comparator를 전달해 커스텀 정렬이 가능하다.
2. comparator는 “앞에 와야 하면 true”를 반환해야 한다.
3. 복합 정렬은 우선순위가 높은 조건부터 비교한다.
4. 전역 변수 대신 람다 캡처를 사용하는 것이 더 안전하고 현대적인 방식이다.
5. 여러 조건 비교에는 std::tie가 유용하다.