[C++ STL] sort 및 특수한 sort 사용법

🔍 std::sort

C++ STL에서 제공하는 정렬 알고리즘으로, 퀵소트(Quick Sort)를 기반으로 하되 최악의 경우에도 $O(n \log n)$의 시간복잡도를 보장하는 하이브리드 정렬 알고리즘이다.

sort가 정의된 헤더

#include <algorithm>

기본 사용법

기본적으로 오름차순 정렬을 수행하며, 비교 함수를 통해 정렬 기준을 커스터마이즈할 수 있다.

// 기본 정렬 (오름차순)
std::sort(first, last);

// 비교 함수를 사용한 정렬
std::sort(first, last, comp);

• first, last: 정렬할 구간의 시작/끝 반복자(보통 begin(), end())
• comp: 비교 함수(선택적). 기본값은 std::less<>로, 오름차순 정렬을 수행
  • rbegin(), rend()을 사용하면 내림차순 정렬을 수행할 수 있다!
• 반환값: void (제자리 정렬)

동작 원리

• 내부적으로 퀵소트를 기반으로 하되, 최악의 경우를 피하기 위해 다음과 같은 최적화를 적용
  1. 작은 구간(보통 16개 이하)에서는 삽입 정렬 사용
  2. 피벗 선택 시 중앙값을 사용하여 최악의 경우 방지
  3. 재귀 깊이가 깊어지면 힙소트로 전환
• 시간복잡도: 평균 $O(n \log n)$, 최악의 경우에도 $O(n \log n)$
• 공간복잡도: $O(\log n)$ (재귀 호출 스택)

예제

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

// 비교 함수 정의
bool compare(int a, int b) {
    return a > b;  // 내림차순 정렬
}

// 구조체 정렬을 위한 비교 함수
struct Person {
    std::string name;
    int age;
};

bool comparePerson(const Person& a, const Person& b) {
    return a.age < b.age;  // 나이 기준 오름차순
}

int main() {
    // 기본 정렬 (오름차순)
    std::vector<int> v1 = {5, 2, 8, 1, 9};
    std::sort(v1.begin(), v1.end());
    // 결과: {1, 2, 5, 8, 9}

    // 내림차순 정렬
    std::vector<int> v2 = {5, 2, 8, 1, 9};
    //std::sort(v2.begin(), v2.end(), compare);
    std::sort(v2.rbegin(), v2.rend());
    // 결과: {9, 8, 5, 2, 1}

    // 람다 함수를 사용한 정렬
    std::vector<int> v3 = {5, 2, 8, 1, 9};
    std::sort(v3.begin(), v3.end(), [](int a, int b) {
        return a > b;  // 내림차순
    });

    // 구조체 정렬
    std::vector<Person> people = {
        {"Alice", 20},
        {"Bob", 18},
        {"Charlie", 25}
    };
    std::sort(people.begin(), people.end(), comparePerson);
    // 결과: Bob(18) -> Alice(20) -> Charlie(25)

    return 0;
}

활용 팁

1. 부분 정렬
   • std::partial_sort: 상위 k개만 정렬
   • std::nth_element: k번째 원소만 올바른 위치로
2. 안정 정렬
   • std::stable_sort: 동일한 값의 상대적 순서 유지
   • 메모리 사용량이 더 많지만, 정렬의 안정성이 필요한 경우 사용
3. 정렬 여부 확인
   • std::is_sorted: 구간이 정렬되어 있는지 확인
   • std::is_sorted_until: 정렬이 깨지는 첫 위치 반환
4. 정렬된 구간 병합
   • std::merge: 두 정렬된 구간을 하나로 병합
   • std::inplace_merge: 제자리에서 두 정렬된 구간 병합
5. 주의사항
   • 비교 함수는 strict weak ordering을 만족해야 함
   • 동일한 값에 대해 false를 반환해야 함
   • 임의 접근 반복자를 요구하므로 std::list 등에서는 사용 불가

성능 최적화 팁

1. 비교 함수 최적화
   • 람다 함수보다 일반 함수가 더 빠를 수 있음
   • 멤버 함수보다 자유 함수가 더 빠를 수 있음
2. 정렬 전 데이터 준비
   • 정렬 전에 데이터를 미리 준비하면 캐시 효율성 향상
   • 구조체 정렬 시 비교에 사용할 멤버를 앞쪽에 배치
3. 메모리 고려
   • 큰 객체 정렬 시 포인터/인덱스로 정렬 후 재배열
   • std::stable_sort는 추가 메모리를 사용하므로 주의

STL 카테고리 내 다른 글 보러가기