C++ Algorithm Sort | "정렬 알고리즘" 가이드

· 11분 읽기 · 수정 중급 튜토리얼
C++ Algorithm Sort | "정렬 알고리즘" 가이드

이 글의 핵심

C++ Algorithm Sort에 대한 실전 가이드입니다.

정렬 알고리즘이란?

정렬 알고리즘 (Sort Algorithm) 은 요소를 특정 순서로 재배열하는 STL 알고리즘입니다. C++은 다양한 정렬 알고리즘을 제공합니다.

#include <algorithm>
#include <vector>

std::vector<int> v = {3, 1, 4, 1, 5};

// 오름차순
std::sort(v.begin(), v.end());

// 내림차순
std::sort(v.begin(), v.end(), std::greater<>());

왜 필요한가?:

  • 데이터 정리: 순서대로 배열
  • 검색 최적화: 이진 탐색 가능
  • 성능: 최적화된 구현
  • 유연성: 커스텀 비교 함수
// ❌ 수동 정렬: 복잡
for (size_t i = 0; i < v.size(); i++) {
    for (size_t j = i + 1; j < v.size(); j++) {
        if (v[i] > v[j]) {
            std::swap(v[i], v[j]);
        }
    }
}

// ✅ STL 정렬: 간결
std::sort(v.begin(), v.end());

정렬 알고리즘 종류:

알고리즘시간 복잡도안정성사용 시나리오
sortO(n log n)❌ 불안정일반적인 정렬
stable_sortO(n log n) ~ O(n log² n)✅ 안정순서 유지 필요
partial_sortO(n log k)❌ 불안정상위 k개만
nth_elementO(n) 평균❌ 불안정n번째 요소만
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

// sort: 빠름
std::sort(v.begin(), v.end());

// stable_sort: 순서 유지
std::stable_sort(v.begin(), v.end());

// partial_sort: 상위 3개
std::partial_sort(v.begin(), v.begin() + 3, v.end());

// nth_element: 중앙값
std::nth_element(v.begin(), v.begin() + v.size() / 2, v.end());

안정성 (Stability):

struct Item {
    int key;
    int value;
};

std::vector<Item> items = {
    {1, 100},
    {2, 200},
    {1, 300}
};

// sort: 불안정 (같은 key 순서 보장 안 됨)
std::sort(items.begin(), items.end(),
     { return a.key < b.key; });
// 결과: {1, 100}, {1, 300} 또는 {1, 300}, {1, 100}

// stable_sort: 안정 (같은 key 순서 유지)
std::stable_sort(items.begin(), items.end(),
     { return a.key < b.key; });
// 결과: {1, 100}, {1, 300} (원래 순서)

sort

#include <algorithm>

std::vector<int> v = {3, 1, 4, 1, 5};

// 기본 정렬
std::sort(v.begin(), v.end());

// 커스텀 비교
std::sort(v.begin(), v.end(),  {
    return a > b;  // 내림차순
});

실전 예시

예시 1: 구조체 정렬

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

struct Person {
    std::string name;
    int age;
};

int main() {
    std::vector<Person> people = {
        {"Charlie", 35},
        {"Alice", 25},
        {"Bob", 30}
    };
    
    // 나이로 정렬
    std::sort(people.begin(), people.end(), 
         {
            return a.age < b.age;
        });
    
    for (const auto& p : people) {
        std::cout << p.name << " (" << p.age << ")" << std::endl;
    }
}

예시 2: stable_sort

#include <algorithm>

struct Student {
    std::string name;
    int score;
};

int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 90},
        {"Charlie", 85},
        {"David", 90}
    };
    
    // 점수로 정렬 (같은 점수는 원래 순서 유지)
    std::stable_sort(students.begin(), students.end(),
         {
            return a.score > b.score;
        });
    
    for (const auto& s : students) {
        std::cout << s.name << ": " << s.score << std::endl;
    }
    // Bob: 90
    // David: 90
    // Alice: 85
    // Charlie: 85
}

예시 3: partial_sort

#include <algorithm>

int main() {
    std::vector<int> v = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    
    // 상위 3개만 정렬
    std::partial_sort(v.begin(), v.begin() + 3, v.end());
    
    std::cout << "상위 3개: ";
    for (int i = 0; i < 3; ++i) {
        std::cout << v[i] << " ";  // 0 1 2
    }
}

예시 4: nth_element

#include <algorithm>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    
    // 중앙값 찾기
    size_t mid = v.size() / 2;
    std::nth_element(v.begin(), v.begin() + mid, v.end());
    
    std::cout << "중앙값: " << v[mid] << std::endl;
}

정렬 종류

// sort: 빠름, 불안정
std::sort(v.begin(), v.end());

// stable_sort: 안정, 느림
std::stable_sort(v.begin(), v.end());

// partial_sort: 부분 정렬
std::partial_sort(v.begin(), v.begin() + n, v.end());

// nth_element: n번째 요소
std::nth_element(v.begin(), v.begin() + n, v.end());

// is_sorted: 정렬 확인
bool sorted = std::is_sorted(v.begin(), v.end());

자주 발생하는 문제

문제 1: 안정성

struct Item {
    int key;
    int value;
};

std::vector<Item> items = {
    {1, 100},
    {2, 200},
    {1, 300}
};

// ❌ sort: 불안정 (같은 key 순서 보장 안 됨)
std::sort(items.begin(), items.end(),
     { return a.key < b.key; });

// ✅ stable_sort: 안정
std::stable_sort(items.begin(), items.end(),
     { return a.key < b.key; });

문제 2: 비교 함수

// ❌ 잘못된 비교 (엄격한 약순서 위반)
std::sort(v.begin(), v.end(),  {
    return a <= b;  // 같을 때 true (잘못됨)
});

// ✅ 올바른 비교
std::sort(v.begin(), v.end(),  {
    return a < b;
});

문제 3: 성능

// sort: O(n log n) 평균
std::sort(v.begin(), v.end());

// stable_sort: O(n log n) ~ O(n log^2 n)
std::stable_sort(v.begin(), v.end());

// partial_sort: O(n log k) (k개 정렬)
std::partial_sort(v.begin(), v.begin() + k, v.end());

// nth_element: O(n) 평균
std::nth_element(v.begin(), v.begin() + n, v.end());

문제 4: 범위

std::vector<int> v = {3, 1, 4, 1, 5};

// ✅ 전체 정렬
std::sort(v.begin(), v.end());

// ✅ 부분 정렬
std::sort(v.begin() + 1, v.begin() + 4);

// ❌ 잘못된 범위
// std::sort(v.end(), v.begin());  // 정의되지 않은 동작

활용 패턴

// 1. 기본 정렬
std::sort(v.begin(), v.end());

// 2. 내림차순
std::sort(v.begin(), v.end(), std::greater<>());

// 3. 안정 정렬
std::stable_sort(v.begin(), v.end());

// 4. 상위 k개
std::partial_sort(v.begin(), v.begin() + k, v.end());

// 5. 중앙값
std::nth_element(v.begin(), v.begin() + mid, v.end());

실무 패턴

패턴 1: 다중 키 정렬

struct Employee {
    std::string department;
    std::string name;
    int salary;
};

std::vector<Employee> employees = {
    {"IT", "Alice", 70000},
    {"HR", "Bob", 60000},
    {"IT", "Charlie", 80000},
    {"HR", "David", 60000}
};

// 부서 → 급여 순으로 정렬
std::sort(employees.begin(), employees.end(),
     {
        if (a.department != b.department) {
            return a.department < b.department;
        }
        return a.salary > b.salary;
    });

패턴 2: Top-K 선택

#include <algorithm>
#include <vector>

template<typename T>
std::vector<T> getTopK(std::vector<T> data, size_t k) {
    if (k >= data.size()) {
        std::sort(data.begin(), data.end(), std::greater<>());
        return data;
    }
    
    std::partial_sort(data.begin(), data.begin() + k, data.end(),
                      std::greater<>());
    
    data.resize(k);
    return data;
}

// 사용
std::vector<int> scores = {85, 92, 78, 95, 88, 90};
auto top3 = getTopK(scores, 3);  // {95, 92, 90}

패턴 3: 범위별 정렬

#include <algorithm>
#include <vector>

struct Task {
    std::string name;
    int priority;
    std::chrono::system_clock::time_point deadline;
};

void sortTasks(std::vector<Task>& tasks) {
    // 1. 우선순위로 그룹화
    std::stable_sort(tasks.begin(), tasks.end(),
         {
            return a.priority > b.priority;
        });
    
    // 2. 각 우선순위 내에서 마감일로 정렬
    auto it = tasks.begin();
    while (it != tasks.end()) {
        int priority = it->priority;
        auto next = std::find_if(it, tasks.end(),
            [priority](const Task& t) { return t.priority != priority; });
        
        std::sort(it, next,
             {
                return a.deadline < b.deadline;
            });
        
        it = next;
    }
}

FAQ

Q1: sort는 무엇인가요?

A: 빠른 정렬 알고리즘입니다. O(n log n) 시간 복잡도이며, 불안정합니다.

std::vector<int> v = {3, 1, 4, 1, 5};
std::sort(v.begin(), v.end());

Q2: stable_sort는?

A: 안정 정렬 알고리즘입니다. 같은 키를 가진 요소의 원래 순서를 유지합니다.

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

Q3: partial_sort는?

A: 상위 k개만 정렬합니다. O(n log k) 시간 복잡도입니다.

// 상위 3개만 정렬
std::partial_sort(v.begin(), v.begin() + 3, v.end());

Q4: 비교 함수는 어떻게 작성하나요?

A: 엄격한 약순서 (Strict Weak Ordering) 를 만족해야 합니다. <를 사용합니다.

// ✅ 올바른 비교
std::sort(v.begin(), v.end(),  {
    return a < b;
});

// ❌ 잘못된 비교
std::sort(v.begin(), v.end(),  {
    return a <= b;  // 같을 때 true (잘못됨)
});

Q5: 성능은?

A:

  • sort: O(n log n) 평균
  • stable_sort: O(n log n) ~ O(n log² n)
  • partial_sort: O(n log k)
  • nth_element: O(n) 평균
// 빠름
std::sort(v.begin(), v.end());

// 느림 (안정성 보장)
std::stable_sort(v.begin(), v.end());

Q6: 정렬 확인은?

A: std::is_sorted 를 사용합니다.

std::vector<int> v = {1, 2, 3, 4, 5};

if (std::is_sorted(v.begin(), v.end())) {
    std::cout << "정렬됨\n";
}

Q7: 커스텀 타입 정렬은?

A: operator<를 오버로드하거나 비교 함수를 제공합니다.

struct Person {
    std::string name;
    int age;
    
    bool operator<(const Person& other) const {
        return age < other.age;
    }
};

std::vector<Person> people;
std::sort(people.begin(), people.end());  // operator< 사용

Q8: 정렬 학습 리소스는?

A:

관련 글: algorithm, comparator, stable_sort.

한 줄 요약: C++ STL 정렬 알고리즘은 효율적인 정렬을 위한 다양한 옵션을 제공합니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

  • C++ Algorithm Partition | “분할 알고리즘” 가이드
  • C++ 알고리즘 | “STL algorithm” 핵심 정리
  • C++ Algorithm Set | “집합 알고리즘” 가이드

실전 팁

실무에서 바로 적용할 수 있는 팁입니다.

디버깅 팁

  • 문제가 발생하면 먼저 컴파일러 경고를 확인하세요
  • 간단한 테스트 케이스로 문제를 재현하세요

성능 팁

  • 프로파일링 없이 최적화하지 마세요
  • 측정 가능한 지표를 먼저 설정하세요

코드 리뷰 팁

  • 코드 리뷰에서 자주 지적받는 부분을 미리 체크하세요
  • 팀의 코딩 컨벤션을 따르세요

실전 체크리스트

실무에서 이 개념을 적용할 때 확인해야 할 사항입니다.

코드 작성 전

  • 이 기법이 현재 문제를 해결하는 최선의 방법인가?
  • 팀원들이 이 코드를 이해하고 유지보수할 수 있는가?
  • 성능 요구사항을 만족하는가?

코드 작성 중

  • 컴파일러 경고를 모두 해결했는가?
  • 엣지 케이스를 고려했는가?
  • 에러 처리가 적절한가?

코드 리뷰 시

  • 코드의 의도가 명확한가?
  • 테스트 케이스가 충분한가?
  • 문서화가 되어 있는가?

이 체크리스트를 활용하여 실수를 줄이고 코드 품질을 높이세요.

이 글에서 다루는 키워드 (관련 검색어)

C++, algorithm, sort, STL, performance 등으로 검색하시면 이 글이 도움이 됩니다.

관련 글

  • C++ 알고리즘 |
  • C++ Algorithm Partition |
  • C++ STL 알고리즘 기초 완벽 가이드 | sort·find
  • C++ STL 알고리즘 완벽 가이드 | sort·transform·accumulate [#54-1]
  • C++ Algorithm Copy |