std::sort와 std::stable_sort는 언제 구분해 써야 하나요?

둘 다 일반 정렬이지만, stable_sort는 동일 키(비교로 같다고 판정된 요소)의 상대 순서를 보존합니다. 순서가 중요한 구조(예: 먼저 넣은 순서 유지)면 stable_sort, 단순히 값 순서만 맞으면 될 때는 보통 sort가 더 낮은 오버헤드로 쓰입니다.

std::partial_sort는 어떤 상황에 적합한가요?

전체를 정렬할 필요 없이 '상위(또는 하위) k개'만 올바른 순서로 얻을 때 씁니다. n이 크고 k가 작을수록 전체 sort보다 유리한 경우가 많습니다.

중앙값이나 k번째 순위만 필요할 때 std::sort 대신 쓰는 것은 무엇인가요?

std::nth_element는 해당 위치에 오는 원소를 찾는 데 맞게 구간을 나누며, 전체 정렬이 필요 없을 때 O(n) 평균에 가깝게 동작해 정렬 전체 O(n log n)보다 가벼울 수 있습니다. 다만 앞/뒤 구간이 완전히 정렬된 상태는 아닙니다.

커스텀 기준(구조체나 복잡한 조건)으로 정렬하려면 어떻게 하나요?

비교 함수(람다, 함수 포인터, operator<가 있는 struct 등)를 세 번째 인자로 넘기면 됩니다. strict weak ordering(자기 자신과는 같다, a<b와 b<a가 동시에 참이면 안 됨)을 지키는 것이 std::sort 계열에 안전합니다.

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

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

이 글의 핵심

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

정렬 알고리즘이란?

정렬 알고리즘 (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());

정렬 알고리즘 종류:

알고리즘	시간 복잡도	안정성	사용 시나리오
`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번째 요소만

C/C++ 예제 코드입니다.

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):

Item 함수의 구현 예제입니다.

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

정렬 종류

C/C++ 예제 코드입니다.

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

C/C++ 예제 코드입니다.

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

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

문제 3: 성능

C/C++ 예제 코드입니다.

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

C/C++ 예제 코드입니다.

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

활용 패턴

C/C++ 예제 코드입니다.

// 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) 를 만족해야 합니다. <를 사용합니다.

C/C++ 예제 코드입니다.

// ✅ 올바른 비교
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) 평균

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

“Effective STL” by Scott Meyers (Item 31-34)
“C++ Primer” by Stanley Lippman
cppreference.com - sort

관련 글: algorithm, comparator, stable_sort.

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

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

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

실전 팁 (C++)

컴파일러 경고를 최대로 켜고(-Wall -Wextra 등 팀 합의), Sanitizer(ASan/UBSan)로 미정의 동작을 조기에 잡습니다.
최적화는 프로파일 결과를 본 뒤에 합니다.
STL <algorithm> 사용 시 반복자 무효화·비교자 일관성을 함께 검토합니다.

실전 체크리스트 (C++)

경고·정적 분석에서 새로운 이슈가 없는가?
빈 범위·단일 원소 등 경계 조건을 테스트했는가?

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

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

심화 부록: 구현·운영 관점

이 부록은 앞선 본문에서 다룬 주제(「C++ Algorithm Sort | ‘정렬 알고리즘’ 가이드」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.

내부 동작과 핵심 메커니즘

flowchart TD
  A[입력·요청·이벤트] --> B[파싱·검증·디코딩]
  B --> C[핵심 연산·상태 전이]
  C --> D[부작용: I/O·네트워크·동시성]
  D --> E[결과·관측·저장]

sequenceDiagram
  participant C as 클라이언트/호출자
  participant B as 경계(런타임·게이트웨이·프로세스)
  participant D as 의존성(API·DB·큐·파일)
  C->>B: 요청/이벤트
  B->>D: 조회·쓰기·RPC
  D-->>B: 지연·부분 실패·재시도 가능
  B-->>C: 응답 또는 오류(코드·상관 ID)

불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.

프로덕션 운영 패턴

영역	운영 관점 질문
관측성	요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가
안전성	입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가
신뢰성	재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가
성능	캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가
배포	롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가
용량	피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가

스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.

확장 예시: 엔드투엔드 미니 시나리오

앞선 본문 주제(「C++ Algorithm Sort | ‘정렬 알고리즘’ 가이드」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.

입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.

handle(request):
  ctx = newCorrelationId()
  validated = validateSchema(request)
  authorize(validated, ctx)
  result = domainCore(validated)
  persistOrEmit(result, idempotentKey)
  recordMetrics(ctx, latency, outcome)
  return result

문제 해결(Troubleshooting)

증상	가능 원인	조치
간헐적 실패	레이스, 타임아웃, 외부 의존성, DNS	최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검
성능 저하	N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스	프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거
메모리 증가	캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납	상한·TTL·힙/FD 스냅샷 비교
빌드·배포만 실패	환경 변수, 권한, 플랫폼 차이, lockfile	CI 로그와 로컬 diff, 런타임·이미지 버전 핀
설정 불일치	프로필·시크릿·기본값, 리전	스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화
데이터 불일치	비멱등 재시도, 부분 쓰기, 캐시 무효화 누락	멱등 키·아웃박스·트랜잭션 경계 재검토

권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.

배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.

Keyboard Shortcuts

이 글의 핵심

정렬 알고리즘이란?

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++)

실전 체크리스트 (C++)

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

관련 글

심화 부록: 구현·운영 관점

내부 동작과 핵심 메커니즘

프로덕션 운영 패턴

확장 예시: 엔드투엔드 미니 시나리오

문제 해결(Troubleshooting)

이 글이 도움이 되셨나요?