[2026] C++ Algorithm Sort | 정렬 알고리즘 가이드

2026년 3월 12일 · 11분 읽기 · 수정 2026년 4월 7일 중급 튜토리얼

이 글의 핵심

C++ sort, stable_sort, partial_sort, nth_element 차이와 쓰임. 커스텀 비교자·부분 정렬·중앙값까지 STL 정렬 가이드.

정렬 알고리즘이란?

정렬 알고리즘 (Sort Algorithm) 은 요소를 특정 순서로 재배열하는 STL 알고리즘입니다. C++은 다양한 정렬 알고리즘을 제공합니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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<>());

왜 필요한가?:

데이터 정리: 순서대로 배열
검색 최적화: 이진 탐색 가능
성능: 최적화된 구현
유연성: 커스텀 비교 함수 아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// ❌ 수동 정렬: 복잡
// 실행 예제
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());

정렬 알고리즘 종류:

알고리즘	시간 복잡도	안정성	사용 시나리오
`sort`	O(n log n)	❌ 불안정	일반적인 정렬
`stable_sort`	O(n log n) ~ O(n log² n)	✅ 안정	순서 유지 필요
`partial_sort`	O(n log k)	❌ 불안정	상위 k개만
`nth_element`	O(n) 평균	❌ 불안정	n번째 요소만
아래 코드는 cpp를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

아래 코드는 cpp를 사용한 구현 예제입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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: 구조체 정렬

다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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

아래 코드는 cpp를 사용한 구현 예제입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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

아래 코드는 cpp를 사용한 구현 예제입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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;
}

정렬 종류

아래 코드는 cpp를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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: 안정성

다음은 cpp를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 비교 함수

아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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

문제 3: 성능

아래 코드는 cpp를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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: 범위

아래 코드는 cpp를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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());  // 정의되지 않은 동작

활용 패턴

아래 코드는 cpp를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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: 다중 키 정렬

다음은 cpp를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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 선택

다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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: 범위별 정렬

다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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) 를 만족해야 합니다. <를 사용합니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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

Q5: 성능은?

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) 평균 아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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

Q6: 정렬 확인은?

A: std::is_sorted 를 사용합니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 조건문으로 분기 처리를 수행합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

std::vector<int> v = {1, 2, 3, 4, 5};
if (std::is_sorted(v.begin(), v.end())) {
    std::cout << "정렬됨\n";
}

Q7: 커스텀 타입 정렬은?

A: operator<를 오버로드하거나 비교 함수를 제공합니다. 아래 코드는 cpp를 사용한 구현 예제입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 정렬 학습 리소스는?

“Effective STL” by Scott Meyers (Item 31-34)
“C++ Primer” by Stanley Lippman
cppreference.com - sort 관련 글: algorithm, comparator, stable_sort. 한 줄 요약: C++ STL 정렬 알고리즘은 효율적인 정렬을 위한 다양한 옵션을 제공합니다.

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

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

실전 팁

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

디버깅 팁

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

성능 팁

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

코드 리뷰 팁

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

실전 체크리스트

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

코드 작성 전

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

코드 작성 중

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

코드 리뷰 시

코드의 의도가 명확한가?
테스트 케이스가 충분한가?
문서화가 되어 있는가? 이 체크리스트를 활용하여 실수를 줄이고 코드 품질을 높이세요.

이 글의 핵심

정렬 알고리즘이란?

sort

실전 예시

예시 1: 구조체 정렬

예시 2: stable_sort

예시 3: partial_sort

예시 4: nth_element

정렬 종류

자주 발생하는 문제

문제 1: 안정성

문제 2: 비교 함수

문제 3: 성능

문제 4: 범위

활용 패턴

실무 패턴

패턴 1: 다중 키 정렬

패턴 2: Top-K 선택

패턴 3: 범위별 정렬

FAQ

Q1: sort는 무엇인가요?

Q2: stable_sort는?

Q3: partial_sort는?

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

Q5: 성능은?

Q6: 정렬 확인은?

Q7: 커스텀 타입 정렬은?

Q8: 정렬 학습 리소스는?

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

실전 팁

디버깅 팁

성능 팁

코드 리뷰 팁

실전 체크리스트

코드 작성 전

코드 작성 중

코드 리뷰 시

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

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

관련 글