pkglog
EN

C++ 정렬 알고리즘 구현과 비교: std::sort의 pdqsort, stable_sort, 병렬 정렬, 기수 정렬

작성 · · 30분 읽기 · 수정 고급 실습

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

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

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

정렬 선택이 성능을 가르는 상황

대량 로그 타임스탬프 정렬

상황: 수십만 건의 로그를 타임스탬프 기준으로 정렬해야 합니다. 버블 정렬이나 선택 정렬을 사용하면 O(n²)로 수 초 이상 걸립니다. 해결: std::sort는 인트로소트(O(n log n))를 사용합니다. 같은 타임스탬프의 로그 순서를 유지해야 하면 std::stable_sort를 사용합니다.

상위 10명만 추출

상황: 100만 명의 점수 중 상위 10명만 필요합니다. 전체를 정렬하면 O(n log n)이지만, 상위 10개만 필요할 때는 비효율적입니다. 해결: std::partial_sort로 O(n log k)에 상위 k개만 정렬합니다. 또는 std::nth_element로 k번째 원소만 올바른 위치에 두며, 그 앞만 정렬할 수 있습니다.

거의 정렬된 데이터

상황: 이미 대부분 정렬된 데이터에 새 원소가 몇 개 추가되었습니다. 일반 퀵소트는 이런 경우 비효율적일 수 있습니다. 해결: 삽입 정렬은 거의 정렬된 데이터에서 O(n)에 가깝게 동작합니다. std::sort의 인트로소트는 작은 구간에서 삽입 정렬로 전환하므로 이미 최적화되어 있습니다.

안정 정렬이 필수인 경우

상황: 이름으로 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]

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

시간·공간 복잡도 비교표

알고리즘평균 시간최악 시간공간안정성
버블 정렬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) 삽입정렬로 전환 (캐시 효율)

세 알고리즘을 섞는 이유는 각자의 약점을 서로 가려 주기 때문입니다. 퀵소트는 평균적으로 가장 빠르고 제자리에서 동작하지만 피벗 선택이 나쁘면 O(n²)로 무너집니다. 힙소트는 최악에도 O(n log n)이지만 메모리 접근이 흩어져 캐시 효율이 나쁩니다. 그래서 평소에는 퀵소트로 달리다가, 재귀가 비정상적으로 깊어지는 “나쁜 입력”을 감지했을 때만 힙소트로 넘어가는 것입니다. 삽입정렬 전환은 원소 몇십 개 수준에서 재귀 호출과 파티션 비용이 비교 비용보다 커지기 때문입니다.

std::sort의 실제 구현: 인트로소트와 pdqsort

C++ 표준은 std::sort에 대해 “비교 횟수 O(n log n)“(C++11부터는 최악 기준)만 요구하고 알고리즘 이름은 정하지 않습니다. 실제로 GCC의 libstdc++와 MSVC STL은 위의 인트로소트를 쓰고, LLVM의 libc++는 최근 버전에서 pdqsort(pattern-defeating quicksort)의 기법을 가져왔습니다. pdqsort는 인트로소트를 기반으로 하되 다음을 추가한 알고리즘입니다.

  • 패턴 감지: 파티션 후 원소가 거의 움직이지 않았다면 “이미 정렬된 구간”으로 보고 제한된 삽입정렬을 시도해, 정렬된 입력이나 역순 입력을 거의 O(n)에 처리합니다.
  • 중복 키 처리: 피벗과 같은 값이 많으면 같은 값 구간을 한 번에 떼어 내서, 값 종류가 적은 입력에서 O(n log n)보다 빠르게 끝냅니다.
  • 분기 없는 파티션(BlockQuicksort): 비교 결과를 오프셋 버퍼에 모아 한 번에 교환해, 무작위 데이터에서 분기 예측 실패를 줄입니다.
  • 적대적 입력 방어: 파티션이 계속 한쪽으로 쏠리면 원소를 섞어 패턴을 깨고, 그래도 안 되면 힙소트로 넘어갑니다.

실무에서 중요한 결론은 “어느 구현이든 최악 O(n log n)은 보장된다”는 점과 같은 값을 가진 원소의 최종 순서는 표준 라이브러리마다 다를 수 있다는 점입니다. 리눅스 서버(libstdc++)와 macOS 개발 머신(libc++)에서 같은 코드가 다른 순서의 결과를 내서 스냅샷 테스트가 한쪽에서만 깨지는 일이 흔히 일어납니다. 결과 순서가 테스트나 출력에 노출된다면 stable_sort를 쓰거나 비교자에 2차 키(예: id)를 넣어 순서를 완전히 결정해 두어야 합니다.

알고리즘 선택 가이드

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

버블·선택·삽입 정렬 구현

아래 O(n²) 알고리즘들을 프로덕션에서 직접 쓸 일은 거의 없지만, 구현해 보면 “안정성은 어디서 생기고 어디서 깨지는가”를 손으로 확인할 수 있습니다. 버블·삽입 정렬은 인접 원소만 바꾸고 같은 값은 건너뛰지 않으므로 안정적이고, 선택 정렬은 멀리 떨어진 원소와 교환하기 때문에 같은 값의 순서가 뒤집힐 수 있습니다. 한 가지 주의할 점은 아래 코드가 모두 n - 1을 size_t로 계산한다는 것입니다. 벡터가 비어 있으면 n - 1이 언더플로해 거대한 수가 되므로, 버블·선택 정렬은 빈 벡터에서 범위 밖 접근을 일으킵니다. 실제로 쓰려면 함수 첫 줄에 if (n < 2) return;을 넣어 두십시오.

버블 정렬 (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;
    }
}

선택 정렬 (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]);
        }
    }
}

삽입 정렬 (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;
    }
}

병합·퀵·힙·계수 정렬 구현

병합 정렬 (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());
}

퀵 정렬 (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);
}

이 Lomuto 파티션 구현은 교과서적이지만 두 가지 함정이 있습니다. 첫째, 마지막 원소를 피벗으로 쓰므로 이미 정렬된 입력에서 매번 한쪽 구간이 비고 재귀 깊이가 n이 됩니다. 10만 개 정도만 넣어도 기본 스택(리눅스 8MB, Windows 1MB)을 넘겨 세그폴트나 Stack overflow 예외로 죽습니다. 둘째, arr[j] <= pivot 조건 때문에 모든 값이 같은 입력도 최악이 됩니다. 같은 값이 전부 왼쪽으로 몰리기 때문입니다. 인트로소트가 재귀 깊이를 감시하고, pdqsort가 중복 키를 따로 처리하는 이유가 바로 이 두 경우입니다. 직접 구현해야 한다면 최소한 median-of-three 피벗과 “작은 쪽 구간만 재귀하고 큰 쪽은 반복문으로 처리”하는 꼬리 재귀 제거를 넣어 스택 깊이를 O(log n)으로 묶어야 합니다.

힙 정렬 (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);
    }
}

계수 정렬 (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;
        }
    }
}

계수 정렬의 k는 원소 수가 아니라 값의 범위라는 점이 함정입니다. counting_sort_auto에 {0, 2'000'000'000} 두 개만 넣어도 20억 칸짜리 count 배열을 할당하려다 std::bad_alloc이 나고, INT_MIN과 INT_MAX가 함께 있으면 max_val - min_val + 1이 int 오버플로(미정의 동작)입니다. 값 범위가 원소 수와 비슷하거나 작을 때만 쓰고, 그렇지 않은 정수 대량 정렬이라면 아래에서 설명할 기수 정렬이 맞는 도구입니다.

기수 정렬 (Radix Sort)과 ska_sort

기수 정렬은 비교를 하지 않고 키를 자릿수(보통 1바이트 = 256개 버킷) 단위로 나눠 분배합니다. 32비트 정수라면 4번의 분배 패스로 끝나므로 O(n·w)이고, 비교 기반 정렬의 하한인 O(n log n)에 묶이지 않습니다.

#include <vector>
#include <cstdint>
#include <array>
// LSD 기수 정렬: 부호 없는 32비트 정수, 바이트 단위 4패스, 안정 정렬
void radix_sort_u32(std::vector<std::uint32_t>& v) {
    std::vector<std::uint32_t> buf(v.size());
    for (int shift = 0; shift < 32; shift += 8) {
        std::array<std::size_t, 257> cnt{};
        for (auto x : v) ++cnt[((x >> shift) & 0xFF) + 1];
        for (int i = 0; i < 256; ++i) cnt[i + 1] += cnt[i];   // 누적합 = 각 버킷 시작 위치
        for (auto x : v) buf[cnt[(x >> shift) & 0xFF]++] = x;
        v.swap(buf);
    }
}

부호 있는 정수는 최상위 비트를 뒤집어(x ^ 0x80000000) 부호 없는 값으로 바꾼 뒤 정렬하고, 부동소수점은 IEEE 754 비트 패턴을 변환하는 트릭이 필요합니다. Malte Skarupke가 공개한 ska_sort는 이런 변환과 MSD(최상위 자리부터) 방식의 제자리 분배를 묶어, 정수·실수·문자열·std::pair/std::tuple 키를 자동으로 처리하는 라이브러리입니다. 비교자 대신 “키를 꺼내는 함수”를 받는다는 점이 std::sort와 가장 큰 차이입니다. 그래서 “대소문자를 무시한 비교”처럼 키로 표현하기 어려운 순서에는 쓸 수 없고, 원소가 수천 개 이하이면 버킷을 세는 고정 비용 때문에 std::sort보다 느린 경우가 많습니다. 도입하기 전에 실제 데이터 분포로 벤치마크를 돌려 보는 것이 필수입니다.

STL 정렬 함수: sort·stable_sort·partial_sort·nth_element

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(),
              [](const Person& a, const Person& b) { return a.age < b.age; });
    return 0;
}

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(),
        [](const LogEntry& a, const LogEntry& b) {
            return a.timestamp < b.timestamp;
        });
}

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

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

다중 키·인덱스·타임스탬프 로그 정렬 예제

다중 키 정렬 (이름 → 점수)

#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(),
        [](const Student& a, const Student& b) {
            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;
}

인덱스 정렬 (원본 순서 유지하며 정렬)

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

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

타임스탬프 로그 정렬 (실전)

#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(),
        [](const LogEntry& a, const LogEntry& b) {
            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;
}

역순 정렬과 범위 지정

#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(),
        [](int a, int b) {
            bool a_even = (a % 2 == 0), b_even = (b % 2 == 0);
            if (a_even != b_even) return a_even;  // 짝수가 앞
            return a < b;
        });
    return 0;
}

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

#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, [](const Product& a, const Product& b) {
        return a.price < b.price;
    });
    for (const auto& p : products) {
        std::cout << p.name << ": " << p.price << "\n";
    }
    return 0;
}

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

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

비교자·반복자 범위·NaN 처리에서 나는 정렬 버그

비교자에서 strict weak ordering 위반

증상: std::sort 호출 시 크래시 또는 무한 루프. 원인: 비교 함수가 a < a를 true로 반환하거나, a < b와 b < a가 동시에 true인 경우.

// ❌ 잘못된 비교자
std::sort(v.begin(), v.end(),
     [](int a, int b) { return a <= b; });  // a <= a 가 true → 위반!
// ✅ 올바른 비교자 (strict weak ordering)
std::sort(v.begin(), v.end(),
     [](int a, int b) { return a < b; });

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

이 버그가 무서운 이유는 작은 입력에서는 멀쩡히 동작하다가, 같은 값이 16개 이상 연속으로 들어오는 순간에만 터진다는 점입니다. libstdc++의 삽입정렬 단계는 “앞에 더 작은 값이 반드시 있다”고 가정하고 경계 검사 없이 왼쪽으로 이동하는데(unguarded insertion), <= 비교자는 그 가정을 깨서 배열 시작 앞의 메모리까지 읽고 씁니다. 저도 이런 크래시를 추적할 때 코어 덤프만 보면 std::__unguarded_linear_insert 안에서 죽어 있어서, 정렬이 아니라 메모리 손상을 의심하며 시간을 쓰기 쉽습니다. 디버그 빌드에서 GCC는 -D_GLIBCXX_DEBUG, MSVC는 기본 디버그 런타임이 비교자를 검사해 invalid comparator 같은 assertion으로 바로 알려 주므로, 정렬 관련 크래시는 먼저 디버그 모드로 재현해 보는 것이 빠릅니다.

반복자 범위 잘못 지정

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

// ❌ 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는 빈 범위를 안전하게 처리합니다.

정렬 중 컨테이너 수정

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

// ❌ 정렬 중에 벡터에 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(), [](int a, int b) { return a < b; });

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(),
    [](const Student& a, const Student& b) {
        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);

포인터/참조 정렬 시 역참조 누락

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

부동소수점 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(),
     [](double x) { return std::isnan(x); }), v.end());
std::sort(v.begin(), v.end());
// ✅ 또는 NaN을 보존하되 항상 맨 뒤로
std::sort(v.begin(), v.end(), [](double a, double b) {
    if (std::isnan(a)) return false;   // NaN은 누구보다도 작지 않음
    if (std::isnan(b)) return true;    // 숫자는 NaN보다 항상 앞
    return a < b;
});

NaN을 버릴 수 없는 데이터(센서 결측값 등)라면 두 번째 방식처럼 NaN을 “가장 큰 값”으로 취급하는 비교자를 쓰면 strict weak ordering이 다시 성립합니다. C++20 이상이라면 std::strong_order(a, b) < 0을 비교자로 쓰는 방법도 있습니다. IEEE 754의 totalOrder를 따르므로 NaN과 -0.0/+0.0까지 일관된 순서가 매겨집니다(음수 부호 NaN은 맨 앞으로 간다는 점은 알아 두십시오).

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

비교자에서 예외 발생

// ❌ 비교자에서 예외 시 정렬 중단, 컨테이너 상태 불명확
std::sort(v.begin(), v.end(), [](int a, int b) {
    if (a < 0 || b < 0) throw std::runtime_error("negative");
    return a < b;
});
// ✅ 비교 전에 유효성 검사, 예외는 피할 것
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a < b;  // 비교자 내부에서는 예외 금지
});

삽입 정렬 컷오프·부분 정렬·이동 의미론

작은 구간은 삽입 정렬

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

상위 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());

비교 비용이 클 때

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

메모리 제약

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

벤치마크 예시

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

이동 의미론 활용

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

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

정렬된 두 시퀀스 병합

이미 정렬된 두 벡터를 합칠 때는 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;
}

정렬 여부 확인

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

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

비교자 재사용·병렬 정렬·정렬 상태 유지 코드

정렬 가능한 타입 설계

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

비교자 객체로 재사용

struct ByAmount {
    bool operator()(const Order& a, const Order& b) const {
        return a.amount < b.amount;
    }
};
std::sort(orders.begin(), orders.end(), ByAmount{});

정렬 전 데이터 검증

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

병렬 정렬 (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는 병렬 실행 정책입니다. 대량 데이터에서 멀티코어 활용이 가능합니다.

한 줄만 바꾸면 되는 것처럼 보이지만, 처음 도입할 때 흔히 막히는 지점이 몇 가지 있습니다.

  • GCC(libstdc++)는 Intel oneTBB가 필요합니다. TBB 개발 패키지를 설치하고 -ltbb로 링크하지 않으면 undefined reference to 'tbb::detail::r1::...' 같은 링크 에러가 납니다. TBB 헤더가 없으면 조용히 순차 구현으로 떨어지는 경우도 있어, “병렬로 바꿨는데 속도가 그대로”라는 증상의 흔한 원인입니다. MSVC는 자체 스레드 풀로 구현되어 추가 라이브러리가 필요 없고, Clang의 libc++는 버전에 따라 지원 수준이 달라 확인이 필요합니다.
  • 비교자는 데이터 경쟁이 없어야 합니다. 여러 스레드가 비교자를 동시에 호출하므로, 비교 횟수를 세는 전역 카운터 같은 공유 상태를 건드리면 미정의 동작입니다.
  • 예외가 나면 std::terminate입니다. 병렬 정책으로 실행되는 알고리즘 안에서 예외가 빠져나오면 호출자에게 전달되지 않고 프로그램이 종료됩니다.
  • 작은 데이터에서는 손해입니다. 작업 분배와 병합 비용이 있어서, 수만 개 이하의 int 정렬은 순차 std::sort가 더 빠른 경우가 흔합니다. 경계가 되는 크기는 CPU와 원소 타입에 따라 크게 달라지므로 직접 측정해야 합니다.

std::stable_sort도 병렬 정책 오버로드가 있으며, 병합 기반이라 병렬화 효율은 오히려 좋은 편입니다.

정렬된 상태 유지 (삽입 시)

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

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

정렬 전략 패턴 (Strategy)

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

#include <algorithm>
#include <vector>
#include <functional>
#include <memory>
#include <string>
struct Student { int id; std::string name; int score; };
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(),
                 [](const Student& a, const Student& b) { return a.id < b.id; });
            break;
        case SortKey::ByName:
            std::sort(students.begin(), students.end(),
                 [](const Student& a, const Student& b) { return a.name < b.name; });
            break;
        case SortKey::ByScore:
            std::sort(students.begin(), students.end(),
                 [](const Student& a, const Student& b) { return a.score > b.score; });
            break;
    }
}

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

범용 정렬 래퍼 (예외 안전)

#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. double 배열에 NaN이 섞여 있으면 std::sort가 왜 문제가 되나요?

A. NaN은 어떤 값과 비교해도 < 결과가 false이기 때문에, NaN이 섞이면 기본 비교가 strict weak ordering을 만족하지 못합니다. 이 경우 정렬 결과가 뒤죽박죽이 되거나 구현에 따라 범위를 벗어난 접근이 일어날 수 있습니다. 정렬 전에 NaN을 제거하거나 std::isnan으로 NaN을 항상 맨 뒤로 보내는 비교자를 직접 작성해야 합니다.

Q. 상위 k개만 필요할 때 partial_sort와 nth_element 중 무엇을 쓰나요?

A. 상위 k개를 정렬된 순서로 보여 줘야 한다면 std::partial_sort를 씁니다. 순서는 상관없이 k번째 경계로 나누기만 하면 된다면 std::nth_element가 더 빠를 수 있고, 이때 n번째 앞쪽 원소들은 n번째보다 작다는 것만 보장되고 서로 정렬되어 있지는 않습니다. k가 n에 가까워지면 partial_sort(내부적으로 힙 사용)는 전체 sort보다 느려지므로, 상위 절반처럼 k가 크다면 nth_element 후 앞부분만 sort하는 조합이 보통 더 빠릅니다.

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

같이 보면 좋은 글