C++ 정렬 알고리즘 완벽 가이드 | sort·stable_sort·직접 구현 [#54-7]

· 32분 읽기 · 수정 고급 실습
C++ 정렬 알고리즘 완벽 가이드 | sort·stable_sort·직접 구현 [#54-7]

이 글의 핵심

C++ 정렬 알고리즘: 버블·삽입·병합·퀵·힙 정렬 구현, std::sort vs stable_sort, 문제 시나리오, 흔한 에러, 성능 팁, 프로덕션 패턴. 대량의 데이터를 다룰 때 정렬은 가장 빈번한 연산 중 하나입니다. 잘못된 알고리즘 선택은 O(n²)로 시간 초과를 유발하고, 같은 값의 순서가 중요한 경우 std::sort만으로는 부족할 수 있습니다.

들어가며: 정렬이 왜 중요한가

”10만 건 로그를 정렬하는데 30초가 걸려요”

대량의 데이터를 다룰 때 정렬은 가장 빈번한 연산 중 하나입니다. 잘못된 알고리즘 선택은 O(n²)로 시간 초과를 유발하고, 같은 값의 순서가 중요한 경우 std::sort만으로는 부족할 수 있습니다. 이 글에서는 기본 정렬 알고리즘의 직접 구현부터 STL 정렬 함수의 올바른 사용, 프로덕션 패턴까지 C++ 정렬의 전부를 다룹니다.

요구 환경: C++17 이상

이 글을 읽으면:

  • 주요 정렬 알고리즘의 원리와 구현을 이해할 수 있습니다.
  • 상황에 맞는 정렬 알고리즘을 선택할 수 있습니다.
  • 흔한 에러를 피하고 성능을 최적화할 수 있습니다.
  • 프로덕션 수준의 정렬 패턴을 적용할 수 있습니다.

실무 적용 경험: 이 글은 대규모 C++ 프로젝트에서 실제로 겪은 문제와 해결 과정을 바탕으로 작성되었습니다. 책이나 문서에서 다루지 않는 실전 함정과 디버깅 팁을 포함합니다.

목차

  1. 문제 시나리오
  2. 정렬 알고리즘 분류와 복잡도
  3. 기본 정렬 알고리즘 구현
  4. 고급 정렬 알고리즘 구현
  5. STL 정렬 함수
  6. 완전한 정렬 예제
  7. 자주 발생하는 에러와 해결법
  8. 성능 최적화 팁
  9. 프로덕션 패턴

1. 문제 시나리오

시나리오 1: 대량 로그 타임스탬프 정렬

상황: 수십만 건의 로그를 타임스탬프 기준으로 정렬해야 합니다. 버블 정렬이나 선택 정렬을 사용하면 O(n²)로 수 초 이상 걸립니다.

해결: std::sort는 인트로소트(O(n log n))를 사용합니다. 같은 타임스탬프의 로그 순서를 유지해야 하면 std::stable_sort를 사용합니다.

시나리오 2: 상위 10명만 추출

상황: 100만 명의 점수 중 상위 10명만 필요합니다. 전체를 정렬하면 O(n log n)이지만, 상위 10개만 필요할 때는 비효율적입니다.

해결: std::partial_sort로 O(n log k)에 상위 k개만 정렬합니다. 또는 std::nth_element로 k번째 원소만 올바른 위치에 두고, 그 앞만 정렬할 수 있습니다.

시나리오 3: 거의 정렬된 데이터

상황: 이미 대부분 정렬된 데이터에 새 원소가 몇 개 추가되었습니다. 일반 퀵소트는 이런 경우 비효율적일 수 있습니다.

해결: 삽입 정렬은 거의 정렬된 데이터에서 O(n)에 가깝게 동작합니다. std::sort의 인트로소트는 작은 구간에서 삽입 정렬로 전환하므로 이미 최적화되어 있습니다.

시나리오 4: 안정 정렬이 필수인 경우

상황: 이름으로 1차 정렬한 뒤, 같은 이름 내에서 점수로 2차 정렬해야 합니다. 정렬이 불안정하면 1차 정렬 결과가 깨집니다.

해결: std::stable_sort를 사용하거나, 2차 키를 포함한 단일 비교자로 한 번에 정렬합니다.

정렬 알고리즘 선택 흐름도

flowchart TD
    A[정렬 필요] --> B{전체 정렬?}
    B -->|예| C{같은 값 순서 중요?}
    B -->|아니오, 상위 k개| D[partial_sort / nth_element]
    C -->|예| E[stable_sort]
    C -->|아니오| F[sort]
    E --> G[O n log n]
    F --> G
    D --> H[O n log k]

2. 정렬 알고리즘 분류와 복잡도

시간·공간 복잡도 비교표

알고리즘평균 시간최악 시간공간안정성
버블 정렬O(n²)O(n²)O(1)✓
선택 정렬O(n²)O(n²)O(1)✗
삽입 정렬O(n²)O(n²)O(1)✓
병합 정렬O(n log n)O(n log n)O(n)✓
퀵 정렬O(n log n)O(n²)O(log n)✗
힙 정렬O(n log n)O(n log n)O(1)✗
std::sort (인트로소트)O(n log n)O(n log n)O(log n)✗

인트로소트(Introsort)란?

std::sort가 사용하는 인트로소트는 퀵소트 + 힙소트 + 삽입정렬의 하이브리드입니다.

  1. 퀵소트로 대부분 정렬
  2. 재귀 깊이가 2⌊log n⌋을 넘으면 힙소트로 전환 (최악 O(n²) 방지)
  3. 구간 크기가 작으면(보통 16~32) 삽입정렬로 전환 (캐시 효율)

알고리즘 선택 가이드

상황권장 알고리즘이유
일반적인 정렬std::sort인트로소트, 대부분 최적
같은 값 순서 유지std::stable_sort안정 정렬
상위 k개만 필요std::partial_sortO(n log k)
k번째 원소만 필요std::nth_elementO(n) 평균
정수, 작은 범위계수 정렬O(n + k)
문자열 정렬std::sort + 커스텀 비교사전순 등

3. 기본 정렬 알고리즘 구현

3.1 버블 정렬 (Bubble Sort)

인접한 두 원소를 비교해 큰 것을 뒤로 보냅니다. 한 번의 패스마다 가장 큰 원소가 끝에 위치합니다.

#include <vector>
#include <utility>

// 버블 정렬: O(n²), 안정 정렬
// - 장점: 구현 간단, 추가 메모리 없음
// - 단점: 대량 데이터에 비효율적
void bubble_sort(std::vector<int>& arr) {
    const size_t n = arr.size();
    for (size_t i = 0; i < n - 1; ++i) {
        bool swapped = false;  // 최적화: 한 패스에 교환 없으면 조기 종료
        for (size_t j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

3.2 선택 정렬 (Selection Sort)

매 패스마다 최소값을 찾아 현재 위치와 교환합니다.

#include <vector>
#include <algorithm>

// 선택 정렬: O(n²), 불안정 정렬
// - 장점: 교환 횟수 최소 (최대 n-1회)
// - 단점: 항상 O(n²), 안정성 없음
void selection_sort(std::vector<int>& arr) {
    const size_t n = arr.size();
    for (size_t i = 0; i < n - 1; ++i) {
        size_t min_idx = i;
        for (size_t j = i + 1; j < n; ++j) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            std::swap(arr[i], arr[min_idx]);
        }
    }
}

3.3 삽입 정렬 (Insertion Sort)

각 원소를 이미 정렬된 앞부분에 올바른 위치에 삽입합니다. 거의 정렬된 데이터에서 매우 빠릅니다.

#include <vector>

// 삽입 정렬: O(n²) 평균, O(n) 거의 정렬됐을 때, 안정 정렬
// - 장점: 작은 n, 거의 정렬된 데이터에 효율적
// - 단점: 역순 데이터에서 최악
void insertion_sort(std::vector<int>& arr) {
    const size_t n = arr.size();
    for (size_t i = 1; i < n; ++i) {
        int key = arr[i];
        size_t j = i;
        while (j > 0 && arr[j - 1] > key) {
            arr[j] = arr[j - 1];
            --j;
        }
        arr[j] = key;
    }
}

4. 고급 정렬 알고리즘 구현

4.1 병합 정렬 (Merge Sort)

분할 정복: 반으로 나누고, 각각 정렬한 뒤 병합합니다. 안정 정렬이며 최악에도 O(n log n)을 보장합니다.

#include <vector>
#include <cstddef>

// 병합: 두 정렬된 구간 [left, mid), [mid, right)를 하나로
void merge(std::vector<int>& arr, std::vector<int>& tmp,
          size_t left, size_t mid, size_t right) {
    size_t i = left, j = mid, k = left;
    while (i < mid && j < right) {
        if (arr[i] <= arr[j]) {  // <= 로 안정성 유지
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    while (i < mid) tmp[k++] = arr[i++];
    while (j < right) tmp[k++] = arr[j++];
    for (size_t idx = left; idx < right; ++idx) {
        arr[idx] = tmp[idx];
    }
}

void merge_sort_impl(std::vector<int>& arr, std::vector<int>& tmp,
                    size_t left, size_t right) {
    if (right - left <= 1) return;
    size_t mid = left + (right - left) / 2;
    merge_sort_impl(arr, tmp, left, mid);
    merge_sort_impl(arr, tmp, mid, right);
    merge(arr, tmp, left, mid, right);
}

void merge_sort(std::vector<int>& arr) {
    std::vector<int> tmp(arr.size());
    merge_sort_impl(arr, tmp, 0, arr.size());
}

4.2 퀵 정렬 (Quick Sort)

피벗을 기준으로 작은 것/큰 것으로 나누고 재귀적으로 정렬합니다. 평균 O(n log n)이지만 최악 O(n²) (이미 정렬된 데이터 + 단순 피벗 선택 시).

#include <vector>
#include <cstddef>
#include <utility>

// 파티션: 피벗보다 작은 것은 왼쪽, 큰 것은 오른쪽
// 피벗은 마지막 원소 사용 (실무에서는 median-of-three 등 사용)
size_t partition(std::vector<int>& arr, size_t low, size_t high) {
    int pivot = arr[high];
    size_t i = low;
    for (size_t j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            std::swap(arr[i++], arr[j]);
        }
    }
    std::swap(arr[i], arr[high]);
    return i;
}

void quick_sort_impl(std::vector<int>& arr, size_t low, size_t high) {
    if (low < high) {
        size_t pi = partition(arr, low, high);
        if (pi > 0) quick_sort_impl(arr, low, pi - 1);
        quick_sort_impl(arr, pi + 1, high);
    }
}

void quick_sort(std::vector<int>& arr) {
    if (arr.size() <= 1) return;
    quick_sort_impl(arr, 0, arr.size() - 1);
}

4.3 힙 정렬 (Heap Sort)

최대 힙을 구성한 뒤, 루트(최대값)를 맨 뒤로 보내며 힙 크기를 줄입니다. 제자리 정렬, 최악에도 O(n log n).

#include <vector>
#include <cstddef>

// 힙에서 부모 인덱스
inline size_t parent(size_t i) { return (i - 1) / 2; }
inline size_t left(size_t i) { return 2 * i + 1; }
inline size_t right(size_t i) { return 2 * i + 2; }

void heapify(std::vector<int>& arr, size_t n, size_t i) {
    size_t largest = i;
    size_t l = left(i), r = right(i);
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heap_sort(std::vector<int>& arr) {
    const size_t n = arr.size();
    for (int i = static_cast<int>(n / 2) - 1; i >= 0; --i) {
        heapify(arr, n, static_cast<size_t>(i));
    }
    for (size_t i = n - 1; i > 0; --i) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

4.4 계수 정렬 (Counting Sort)

정수이고 값의 범위가 작을 때 O(n + k)로 동작합니다. k는 값의 범위입니다.

#include <vector>
#include <algorithm>
#include <limits>

// 값 범위가 [0, max_val]로 알려진 경우
void counting_sort(std::vector<int>& arr, int max_val) {
    std::vector<int> count(max_val + 1, 0);
    for (int x : arr) ++count[x];

    size_t idx = 0;
    for (int v = 0; v <= max_val; ++v) {
        for (int c = 0; c < count[v]; ++c) {
            arr[idx++] = v;
        }
    }
}

// 범위를 모를 때: min/max 스캔 후 정규화
void counting_sort_auto(std::vector<int>& arr) {
    if (arr.empty()) return;
    int min_val = *std::min_element(arr.begin(), arr.end());
    int max_val = *std::max_element(arr.begin(), arr.end());
    int range = max_val - min_val + 1;

    std::vector<int> count(range, 0);
    for (int x : arr) ++count[x - min_val];

    size_t idx = 0;
    for (int i = 0; i < range; ++i) {
        for (int c = 0; c < count[i]; ++c) {
            arr[idx++] = min_val + i;
        }
    }
}

5. STL 정렬 함수

5.1 std::sort

기본 정렬. 불안정, 대부분의 경우 최선의 선택입니다.

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

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    std::sort(v.begin(), v.end());
    for (int x : v) std::cout << x << " ";  // 1 2 3 5 7 8 9
    std::cout << "\n";

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

    // 커스텀 비교 (람다)
    struct Person { std::string name; int age; };
    std::vector<Person> people = {{"Kim", 30}, {"Lee", 25}, {"Park", 35}};
    std::sort(people.begin(), people.end(),
               { return a.age < b.age; });
    return 0;
}

5.2 std::stable_sort

안정 정렬. 같은 값의 원래 순서를 유지합니다. 병합 정렬 기반, 추가 O(n) 메모리 사용.

#include <algorithm>
#include <vector>

struct LogEntry {
    int timestamp;
    int level;  // 같은 timestamp일 때 level 순서 유지 필요
    std::string msg;
};

void sort_logs(std::vector<LogEntry>& logs) {
    // timestamp로 정렬, 같은 timestamp면 원래 순서(level) 유지
    std::stable_sort(logs.begin(), logs.end(),
         {
            return a.timestamp < b.timestamp;
        });
}

5.3 std::partial_sort

상위 k개만 정렬합니다. 나머지는 정렬되지 않은 상태로 둡니다.

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

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

5.4 std::nth_element

n번째 원소만 올바른 위치에 두고, 그 앞은 모두 n번째보다 작고, 뒤는 모두 크게 만듭니다. 상위 k개가 필요할 때 partial_sort보다 빠를 수 있습니다.

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

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    // 3번째로 작은 원소(0-based)를 올바른 위치에
    std::nth_element(v.begin(), v.begin() + 2, v.end());
    std::cout << "3번째로 작은 값: " << v[2] << "\n";  // 3
    return 0;
}

6. 완전한 정렬 예제

예제 1: 다중 키 정렬 (이름 → 점수)

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

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

int main() {
    std::vector<Student> students = {
        {"Kim", 85}, {"Lee", 90}, {"Kim", 78}, {"Park", 92}, {"Lee", 88}
    };

    // 1차: 이름 오름차순, 2차: 점수 내림차순
    std::sort(students.begin(), students.end(),
         {
            if (a.name != b.name) return a.name < b.name;
            return a.score > b.score;
        });

    for (const auto& s : students) {
        std::cout << s.name << " " << s.score << "\n";
    }
    return 0;
}

예제 2: 인덱스 정렬 (원본 순서 유지하며 정렬)

원본 배열을 건드리지 않고, 정렬된 순서의 인덱스만 얻고 싶을 때:

#include <algorithm>
#include <vector>
#include <numeric>
#include <iostream>

std::vector<size_t> argsort(const std::vector<int>& arr) {
    std::vector<size_t> indices(arr.size());
    std::iota(indices.begin(), indices.end(), 0);
    std::sort(indices.begin(), indices.end(),
        [&arr](size_t i, size_t j) { return arr[i] < arr[j]; });
    return indices;
}

int main() {
    std::vector<int> v = {30, 10, 50, 20, 40};
    auto idx = argsort(v);
    for (size_t i : idx) std::cout << v[i] << " ";  // 10 20 30 40 50
    std::cout << "\n";
    return 0;
}

예제 3: 타임스탬프 로그 정렬 (실전)

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

struct LogEntry {
    std::string timestamp;  // "2026-05-02T14:30:00"
    int level;
    std::string message;
};

bool parse_and_compare(const std::string& a, const std::string& b) {
    // ISO 8601 형식이면 문자열 비교로 충분
    return a < b;
}

void sort_logs_by_time(std::vector<LogEntry>& logs) {
    std::stable_sort(logs.begin(), logs.end(),
         {
            return parse_and_compare(a.timestamp, b.timestamp);
        });
}

int main() {
    std::vector<LogEntry> logs = {
        {"2026-05-02T14:30:00", 1, "Start"},
        {"2026-05-02T14:29:00", 2, "Config"},
        {"2026-05-02T14:30:00", 3, "Ready"}
    };
    sort_logs_by_time(logs);
    for (const auto& e : logs) {
        std::cout << e.timestamp << " [" << e.level << "] " << e.message << "\n";
    }
    return 0;
}

예제 4: 역순 정렬과 범위 지정

#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};

    // 일부 구간만 정렬 [v.begin()+2, v.begin()+7)
    std::sort(v.begin() + 2, v.begin() + 7);

    // 전체 역순 (greater 사용)
    std::sort(v.begin(), v.end(), std::greater<int>());

    // 람다로 커스텀: 짝수 우선, 그 다음 오름차순
    std::sort(v.begin(), v.end(),
         {
            bool a_even = (a % 2 == 0), b_even = (b % 2 == 0);
            if (a_even != b_even) return a_even;  // 짝수가 앞
            return a < b;
        });
    return 0;
}

예제 5: 구조체 배열 정렬 (멤버 포인터 활용)

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

struct Product {
    int id;
    std::string name;
    double price;
};

// 정렬 기준을 템플릿으로 받는 범용 함수
template<typename T, typename Cmp>
void sort_by(std::vector<T>& v, Cmp cmp) {
    std::sort(v.begin(), v.end(), cmp);
}

int main() {
    std::vector<Product> products = {
        {3, "Keyboard", 89000},
        {1, "Mouse", 35000},
        {2, "Monitor", 250000}
    };

    sort_by(products,  {
        return a.price < b.price;
    });

    for (const auto& p : products) {
        std::cout << p.name << ": " << p.price << "\n";
    }
    return 0;
}

예제 6: 정렬 알고리즘 벤치마크 (전체 비교)

#include <algorithm>
#include <vector>
#include <chrono>
#include <random>
#include <iostream>
#include <functional>

template<typename Func>
double measure_ms(Func&& f) {
    auto start = std::chrono::high_resolution_clock::now();
    f();
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration<double, std::milli>(end - start).count();
}

void run_benchmark() {
    const size_t n = 100'000;
    std::vector<int> original(n);
    std::mt19937 gen(42);
    std::uniform_int_distribution<> dis(0, 1'000'000);
    for (auto& x : original) x = dis(gen);

    auto v = original;
    double t_sort = measure_ms([&] { std::sort(v.begin(), v.end()); });

    v = original;
    double t_stable = measure_ms([&] { std::stable_sort(v.begin(), v.end()); });

    v = original;
    double t_partial = measure_ms([&] {
        std::partial_sort(v.begin(), v.begin() + 10, v.end());
    });

    std::cout << "n=" << n << ":\n";
    std::cout << "  sort:      " << t_sort << " ms\n";
    std::cout << "  stable:    " << t_stable << " ms\n";
    std::cout << "  partial(10): " << t_partial << " ms\n";
}

7. 자주 발생하는 에러와 해결법

에러 1: 비교자에서 strict weak ordering 위반

증상: std::sort 호출 시 크래시 또는 무한 루프.

원인: 비교 함수가 a < a를 true로 반환하거나, a < b와 b < a가 동시에 true인 경우.

// ❌ 잘못된 비교자
std::sort(v.begin(), v.end(),
     { return a <= b; });  // a <= a 가 true → 위반!

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

규칙: comp(a, a)는 항상 false, comp(a, b) == true이면 comp(b, a) == false.

에러 2: 반복자 범위 잘못 지정

증상: 런타임 에러 또는 정렬되지 않은 결과.

// ❌ end를 포함시킴 (반개구간 [begin, end) 가 정석)
std::sort(v.begin(), v.end() + 1);  // 범위 초과!

// ❌ 빈 벡터에 sort
std::vector<int> empty;
std::sort(empty.begin(), empty.end());  // OK (빈 범위는 안전)

해결: 항상 [begin, end) 반개구간을 사용합니다. std::sort는 빈 범위를 안전하게 처리합니다.

에러 3: 정렬 중 컨테이너 수정

증상: 미정의 동작, 크래시.

// ❌ 정렬 중에 벡터에 push
std::sort(v.begin(), v.end(), [&v](int a, int b) {
    v.push_back(0);  // 절대 금지!
    return a < b;
});

// ✅ 비교자에서는 외부 상태 변경 금지
std::sort(v.begin(), v.end(),  { return a < b; });

에러 4: stable_sort 필요할 때 sort 사용

증상: 다중 키 정렬 시 1차 키 순서가 깨짐.

// ❌ 이름으로 정렬한 뒤 점수로 정렬 → 1차 결과 깨짐
std::sort(students.begin(), students.end(), by_name);
std::sort(students.begin(), students.end(), by_score);

// ✅ 한 번에 2차 키까지 포함해 정렬
std::sort(students.begin(), students.end(),
     {
        if (a.name != b.name) return a.name < b.name;
        return a.score < b.score;
    });

// 또는 stable_sort로 2번 정렬 (나중 키부터)
std::stable_sort(students.begin(), students.end(), by_score);
std::stable_sort(students.begin(), students.end(), by_name);

에러 5: 포인터/참조 정렬 시 역참조 누락

// ❌ 포인터를 정렬하면 주소값으로 정렬됨
std::vector<int*> ptrs = {&a, &b, &c};
std::sort(ptrs.begin(), ptrs.end());  // 값이 아닌 주소 비교!

// ✅ 역참조해서 값으로 비교
std::sort(ptrs.begin(), ptrs.end(),
     { return *a < *b; });

에러 6: 부동소수점 NaN 처리

#include <cmath>
#include <algorithm>
#include <vector>

// ❌ NaN이 있으면 비교 결과가 불안정 → 미정의 동작
std::vector<double> v = {1.0, NAN, 2.0, 3.0};
std::sort(v.begin(), v.end());  // 위험!

// ✅ NaN 제거 후 정렬
v.erase(std::remove_if(v.begin(), v.end(),
     { return std::isnan(x); }), v.end());
std::sort(v.begin(), v.end());

에러 7: partial_sort 범위 오류

// ❌ k가 size보다 크면 undefined behavior
std::vector<int> v = {1, 2, 3};
std::partial_sort(v.begin(), v.begin() + 10, v.end());  // UB!

// ✅ k를 size로 제한
size_t k = std::min(size_t(10), v.size());
std::partial_sort(v.begin(), v.begin() + k, v.end());

에러 8: 비교자에서 예외 발생

// ❌ 비교자에서 예외 시 정렬 중단, 컨테이너 상태 불명확
std::sort(v.begin(), v.end(),  {
    if (a < 0 || b < 0) throw std::runtime_error("negative");
    return a < b;
});

// ✅ 비교 전에 유효성 검사, 예외는 피할 것
std::sort(v.begin(), v.end(),  {
    return a < b;  // 비교자 내부에서는 예외 금지
});

8. 성능 최적화 팁

팁 1: 작은 구간은 삽입 정렬

n이 작을 때(예: 32 이하) 삽입 정렬이 캐시 효율로 인해 퀵소트보다 빠를 수 있습니다. std::sort는 이미 이 전략을 사용합니다.

팁 2: 상위 k개만 필요하면 partial_sort / nth_element

// 전체 정렬 O(n log n) vs 상위 10개만 O(n log 10)
std::partial_sort(v.begin(), v.begin() + 10, v.end());

팁 3: 비교 비용이 클 때

비교 연산이 비싼 경우(예: 문자열, 복잡한 구조체), 인덱스 정렬로 비교 횟수를 줄이거나, 래딕스 정렬을 고려합니다.

팁 4: 메모리 제약

std::stable_sort는 O(n) 추가 메모리를 사용합니다. 메모리가 극히 제한적이면 std::sort를 사용하고, 다중 키 정렬은 단일 비교자로 처리합니다.

팁 5: 벤치마크 예시

#include <algorithm>
#include <vector>
#include <chrono>
#include <random>
#include <iostream>

void benchmark_sort(size_t n) {
    std::vector<int> v(n);
    std::mt19937 gen(42);
    std::uniform_int_distribution<> dis(0, 1000000);
    for (auto& x : v) x = dis(gen);

    auto start = std::chrono::high_resolution_clock::now();
    std::sort(v.begin(), v.end());
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "n=" << n << " sort: " << ms << " ms\n";
}

팁 6: 이동 의미론 활용

정렬할 요소가 무거운 객체(예: std::string, 커스텀 타입)일 때, 비교자에서 참조로 받아 복사를 피합니다.

// ✅ const 참조로 비교
std::sort(items.begin(), items.end(),
     {
        return a.key() < b.key();
    });

팁 7: 정렬된 두 시퀀스 병합

이미 정렬된 두 벡터를 합칠 때는 std::merge가 정렬보다 효율적입니다.

#include <algorithm>
#include <vector>

std::vector<int> merge_sorted(const std::vector<int>& a,
                              const std::vector<int>& b) {
    std::vector<int> result(a.size() + b.size());
    std::merge(a.begin(), a.end(), b.begin(), b.end(), result.begin());
    return result;
}

팁 8: 정렬 여부 확인

이미 정렬되어 있는지 확인할 때는 std::is_sorted를 사용합니다.

if (std::is_sorted(v.begin(), v.end())) {
    // 이미 정렬됨, 스킵
} else {
    std::sort(v.begin(), v.end());
}

9. 프로덕션 패턴

패턴 1: 정렬 가능한 타입 설계

struct Order {
    int id;
    std::chrono::system_clock::time_point created_at;
    double amount;

    // 기본 비교: created_at 기준
    bool operator<(const Order& other) const {
        return created_at < other.created_at;
    }
};

// 사용
std::vector<Order> orders;
std::sort(orders.begin(), orders.end());

패턴 2: 비교자 객체로 재사용

struct ByAmount {
    bool operator()(const Order& a, const Order& b) const {
        return a.amount < b.amount;
    }
};

std::sort(orders.begin(), orders.end(), ByAmount{});

패턴 3: 정렬 전 데이터 검증

void safe_sort(std::vector<int>& v) {
    if (v.empty()) return;
    // NaN, Inf 등 특수값 체크 (부동소수점인 경우)
    std::sort(v.begin(), v.end());
}

패턴 4: 병렬 정렬 (C++17)

#include <algorithm>
#include <execution>
#include <vector>

void parallel_sort(std::vector<int>& v) {
    std::sort(std::execution::par, v.begin(), v.end());
}

std::execution::par는 병렬 실행 정책입니다. 대량 데이터에서 멀티코어 활용이 가능합니다.

패턴 5: 정렬된 상태 유지 (삽입 시)

새 원소를 삽입할 때마다 정렬된 상태를 유지하려면:

#include <algorithm>
#include <vector>

template<typename T>
void insert_sorted(std::vector<T>& v, const T& value) {
    auto it = std::lower_bound(v.begin(), v.end(), value);
    v.insert(it, value);
}

패턴 6: 정렬 전략 패턴 (Strategy)

런타임에 정렬 기준을 바꿀 때:

#include <algorithm>
#include <vector>
#include <functional>
#include <memory>

enum class SortKey { ById, ByName, ByScore };

void sort_with_strategy(std::vector<Student>& students, SortKey key) {
    switch (key) {
        case SortKey::ById:
            std::sort(students.begin(), students.end(),
                 { return a.id < b.id; });
            break;
        case SortKey::ByName:
            std::sort(students.begin(), students.end(),
                 { return a.name < b.name; });
            break;
        case SortKey::ByScore:
            std::sort(students.begin(), students.end(),
                 { return a.score > b.score; });
            break;
    }
}

패턴 7: RAII 스코프 정렬 (디버깅용)

정렬 전후 상태를 로깅할 때:

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

template<typename It>
class SortScope {
    It begin_, end_;
    bool sorted_ = false;
public:
    SortScope(It b, It e) : begin_(b), end_(e) {}
    void sort() {
        std::sort(begin_, end_);
        sorted_ = true;
    }
    ~SortScope() {
        if (sorted_ && !std::is_sorted(begin_, end_)) {
            std::cerr << "Warning: sort invariant violated\n";
        }
    }
};

패턴 8: 범용 정렬 래퍼 (예외 안전)

#include <algorithm>
#include <vector>
#include <stdexcept>

template<typename T, typename Compare = std::less<>>
void safe_sort(std::vector<T>& v, Compare cmp = {}) {
    if (v.size() > 1'000'000) {
        throw std::invalid_argument("Vector too large for safe_sort");
    }
    std::sort(v.begin(), v.end(), cmp);
}

정렬 알고리즘 동작 시각화

퀵소트 파티션 과정

flowchart LR
    subgraph before[파티션 전]
        A1[5] A2[2] A3[8] A4[1] A5[9] A6[3] A7[7]
    end
    subgraph pivot[피벗=7]
        P[7]
    end
    subgraph after[파티션 후]
        B1[5] B2[2] B3[1] B4[3] B5[7] B6[9] B7[8]
    end
    before --> pivot
    pivot --> after

병합 정렬 분할-병합

flowchart TB
    A[[5,2,8,1]] --> B[[5,2]]
    A --> C[[8,1]]
    B --> D[[5]]
    B --> E[[2]]
    C --> F[[8]]
    C --> G[[1]]
    D --> H[[2,5]]
    E --> H
    F --> I[[1,8]]
    G --> I
    H --> J[[1,2,5,8]]
    I --> J

정리

항목설명
기본 알고리즘버블·선택·삽입 O(n²), 작은 n이나 교육용
고급 알고리즘병합·퀵·힙 O(n log n), 직접 구현 시 참고
STLsort(일반), stable_sort(안정), partial_sort(상위 k개)
에러strict weak ordering, 반복자 범위, 정렬 중 수정 금지
성능상위 k개→partial_sort, 비교 비용→인덱스 정렬
프로덕션operator<, 비교자 객체, 병렬 정렬, insert_sorted

핵심 원칙:

  1. 대부분의 경우 std::sort 사용
  2. 같은 값 순서가 중요하면 std::stable_sort
  3. 상위 k개만 필요하면 std::partial_sort 또는 std::nth_element
  4. 비교자는 strict weak ordering 준수
  5. 직접 구현은 교육 목적 외에는 STL 활용

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. 대량 데이터 정렬, 로그/이벤트 타임스탬프 정렬, 상위 N개 추출 등에 활용합니다. std::sort가 대부분의 경우 최선이지만, 안정 정렬이 필요하거나 상위 k개만 필요할 때는 stable_sort, partial_sort를 선택합니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference - sort와 std::sort 구현 분석을 참고하세요.

한 줄 요약: C++ 정렬의 기본부터 프로덕션 패턴까지, 상황에 맞는 알고리즘 선택이 핵심입니다.

관련 글

  • C++ 정렬·검색 완벽 가이드 | 퀵소트·병합정렬·이진탐색·STL [실전]
  • C++ Algorithm Sort |
  • C++ Algorithm Heap |
  • C++ Algorithm Partition |
... 996 lines not shown ... Token usage: 63706/1000000; 936294 remaining Start-Sleep -Seconds 3