pkglog
EN

STL 정렬과 검색 함께 쓰기: sort·stable_sort·병렬 정렬과 lower_bound·upper_bound

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

들어가며: 정렬·검색 선택의 함정

대용량 데이터를 정렬하거나 검색할 때 잘못된 알고리즘을 고르면 입력이 커지는 순간 프로그램이 사실상 멈춥니다. 100만 건이면 O(n²) 정렬은 비교만 약 5천억 번이 필요하고, O(n log n) 정렬은 약 2천만 번이면 끝납니다. 차이가 상수배가 아니라 수만 배라서, 작은 테스트 데이터에서는 드러나지 않다가 운영 데이터에서 갑자기 터지는 전형적인 문제입니다.

flowchart TD
  subgraph wrong[❌ 잘못된 선택]
    W1[버블/삽입 정렬] --> W2["O(n²)"]
    W2 --> W3[100만 건 → 비교 약 5천억 회]
    W3 --> W4["순차 검색 O(n)"]
  end
  subgraph right[✅ 올바른 선택]
    R1[퀵소트/병합정렬] --> R2["O(n log n)"]
    R2 --> R3[100만 건 → 비교 약 2천만 회]
    R3 --> R4["이진 탐색 O(log n)"]
  end

이 글은 실제로 자주 만나는 상황에서 시작해, 퀵·병합·기수·하이브리드 정렬의 C++ 구현, lower_bound 계열 이진 탐색, 비교자와 경계 처리에서 흔히 하는 실수, 그리고 표준 라이브러리를 언제 믿고 언제 직접 구현을 고려할지를 차례로 다룹니다. 직접 구현은 동작 원리를 이해하기 위한 것이고, 실무에서는 거의 항상 std::sort와 std::lower_bound가 출발점입니다.

요구 환경: 예제에 구조화된 바인딩과 std::optional을 쓰므로 C++17 이상으로 컴파일합니다.

정렬·검색 선택을 잘못하는 상황들

대용량 로그 파일 정렬

상황: 100만 건의 로그를 타임스탬프 기준으로 정렬해야 합니다. 잘못된 접근: 버블 정렬이나 선택 정렬을 쓰면 O(n²)라 입력이 커질수록 시간이 제곱으로 늘어납니다. 해결: std::sort 또는 퀵소트/병합정렬 O(n log n) 사용. 로그 레코드가 크다면 레코드 자체보다 (타임스탬프, 인덱스) 쌍을 정렬하는 편이 이동 비용이 작습니다.

정렬된 배열에서 범위 검색

상황: 이미 정렬된 사용자 ID 목록에서 “1000 이상 2000 미만”인 사용자 수를 찾아야 합니다. 잘못된 접근: 순차 탐색 O(n)으로 전체를 훑습니다. 해결: lower_bound와 upper_bound로 O(log n)에 범위 경계를 찾으며, upper_bound - lower_bound로 개수 계산.

안정 정렬이 필요한 경우

상황: 이름으로 정렬한 뒤, 같은 이름 내에서는 가입일 순으로 유지해야 합니다. 잘못된 접근: std::sort는 불안정 정렬이라 같은 키의 상대 순서가 바뀔 수 있습니다. 해결: std::stable_sort 또는 병합정렬 사용. 동일 키의 원래 순서를 유지합니다.

정수만 있는 데이터 (기수 정렬)

상황: 0~999999 범위의 정수 100만 개를 정렬해야 합니다. 잘못된 접근: 비교 기반 정렬은 O(n log n) 하한이 있습니다. 해결: 기수 정렬 O(n × k)로, k가 작으면 비교 정렬보다 빠를 수 있습니다. 다만 LSD 기수 정렬은 패스마다 출력 버퍼의 여러 버킷 위치에 흩어서 쓰기 때문에 캐시 친화적이지 않고, 입력 크기만큼 추가 메모리가 필요합니다. 입력이 캐시에 들어갈 만큼 작으면 오히려 std::sort가 빠른 경우가 흔하므로 반드시 측정해야 합니다.

부분 정렬만 필요한 경우

상황: 상위 10명만 필요할 때 100만 명 전체를 정렬하는 것은 낭비입니다. 잘못된 접근: std::sort로 전체 정렬 후 앞 10개만 사용. 해결: std::partial_sort(O(n log k), 상위 k개를 정렬된 상태로) 또는 std::nth_element(평균 O(n), k번째 위치만 확정하고 앞쪽은 순서 무관)를 씁니다.

알고리즘 선택 가이드

문제 유형추천 알고리즘시간 복잡도
일반 정렬std::sort (IntroSort)O(n log n)
안정 정렬 필요std::stable_sortO(n log n)
상위 k개만std::partial_sort, nth_elementO(n log k), O(n)
정수/문자열 (기수)기수 정렬O(n × k)
정렬된 배열 검색lower_bound, upper_boundO(log n)
범위 개수equal_rangeO(log n)

STL 정렬·검색 함수 개요

STL 정렬 함수 비교

flowchart LR
  subgraph sort["std::sort"]
    S1[불안정] --> S2[IntroSort]
    S2 --> S3[퀵+힙+삽입]
  end
  subgraph stable["std::stable_sort"]
    ST1[안정] --> ST2[병합정렬]
  end
  subgraph partial["std::partial_sort"]
    P1[상위 k개] --> P2[힙 기반]
  end

기본 STL 사용법

#include <algorithm>
#include <vector>
// 1. 기본 오름차순 정렬
std::vector<int> v = {5, 2, 8, 1, 9};
std::sort(v.begin(), v.end());
// v = {1, 2, 5, 8, 9}
// 2. 커스텀 비교자 (내림차순)
std::sort(v.begin(), v.end(), std::greater<int>());
// v = {9, 8, 5, 2, 1}
// 3. 람다로 복합 조건
struct Person { std::string name; int age; };
std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Alice", 20}};
std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) {
        if (a.name != b.name) return a.name < b.name;
        return a.age < b.age;
    });
// 4. 정렬된 배열에서 검색
auto it = std::lower_bound(v.begin(), v.end(), 5);  // >= 5인 첫 위치
auto jt = std::upper_bound(v.begin(), v.end(), 5);  // > 5인 첫 위치
// [it, jt) 구간에 5와 같은 값들

마지막 두 줄에는 함정이 하나 있습니다. 바로 위에서 std::greater<int>()로 내림차순 정렬한 v에 기본 비교(<)로 lower_bound를 호출하고 있습니다. 이진 탐색은 정렬에 쓴 것과 같은 비교자를 받아야 올바르게 동작하므로, 이 경우 std::lower_bound(v.begin(), v.end(), 5, std::greater<int>())로 써야 합니다. 비교자가 다르면 컴파일은 되지만 결과가 틀리고, 표준상으로는 전제 조건 위반입니다. 실무에서 가장 찾기 어려운 이진 탐색 버그가 이 유형입니다.

퀵·병합·기수·하이브리드 정렬 구현

퀵소트 (QuickSort)

핵심 아이디어: 피벗을 선택해 분할하며, 왼쪽은 피벗보다 작게, 오른쪽은 크게 배치한 뒤 재귀적으로 정렬합니다.

flowchart TD
  A[5,2,8,1,9] --> B[피벗 5]
  B --> C["2,1 | 5 | 8,9"]
  C --> D[1,2] --> E[정렬됨]
  C --> F[8,9] --> G[정렬됨]
#include <vector>
#include <algorithm>
// Lomuto 분할: 피벗을 끝 원소로, 간단하지만 최악 O(n²) 가능
int partitionLomuto(std::vector<int>& a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo;
    for (int j = lo; j < hi; ++j) {
        if (a[j] <= pivot) {
            std::swap(a[i], a[j]);
            ++i;
        }
    }
    std::swap(a[i], a[hi]);
    return i;
}
// Hoare 분할: 양쪽에서 접근, 더 효율적
int partitionHoare(std::vector<int>& a, int lo, int hi) {
    int pivot = a[lo + (hi - lo) / 2];  // 중간값 피벗 (최악 방지)
    int i = lo - 1, j = hi + 1;
    while (true) {
        do ++i; while (a[i] < pivot);
        do --j; while (a[j] > pivot);
        if (i >= j) return j;
        std::swap(a[i], a[j]);
    }
}
void quicksort(std::vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partitionHoare(a, lo, hi);
    quicksort(a, lo, p);
    quicksort(a, p + 1, hi);
}
// 사용 예시
void example_quicksort() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    quicksort(v, 0, static_cast<int>(v.size()) - 1);
    // v = {1, 2, 3, 5, 7, 8, 9}
}

Lomuto 분할은 구현이 짧지만, 모든 원소가 같은 배열에서 a[j] <= pivot이 항상 참이라 한쪽으로만 분할되어 O(n²)이 됩니다. Hoare 분할은 같은 값을 만나면 양쪽 모두 멈추고 교환하므로 중복이 많아도 균형 있게 나뉩니다. 대신 Hoare 분할이 반환하는 p는 피벗의 최종 위치가 아니기 때문에 재귀를 [lo, p]와 [p+1, hi]로 나눠야 합니다. Lomuto처럼 [lo, p-1], [p+1, hi]로 나누면 원소가 빠지거나 무한 재귀에 빠집니다. 두 분할 방식을 섞어 쓰다 보면 이 차이를 놓치기 쉽습니다.

병합정렬 (Merge Sort)

핵심 아이디어: 배열을 반으로 나누고, 각각 정렬한 뒤 병합합니다. 안정 정렬이며 최악에도 O(n log n)을 보장합니다.

#include <vector>
void merge(std::vector<int>& a, int lo, int mid, int hi,
          std::vector<int>& tmp) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];  // <= 로 안정성 유지
        else              tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (int idx = lo; idx <= hi; ++idx)
        a[idx] = tmp[idx];
}
void mergesort(std::vector<int>& a, int lo, int hi, std::vector<int>& tmp) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergesort(a, lo, mid, tmp);
    mergesort(a, mid + 1, hi, tmp);
    merge(a, lo, mid, hi, tmp);
}
void mergesort(std::vector<int>& a) {
    std::vector<int> tmp(a.size());
    mergesort(a, 0, static_cast<int>(a.size()) - 1, tmp);
}
// 사용 예시
void example_mergesort() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    mergesort(v);
    // v = {1, 2, 3, 5, 7, 8, 9}
}

a[i] <= a[j]에서 <=가 안정성의 핵심입니다. 같은 값이면 왼쪽 절반(원래 앞에 있던 것)을 먼저 가져오기 때문입니다. 이것을 <로 바꾸면 결과는 여전히 정렬되지만 같은 키의 순서가 뒤바뀌어 안정 정렬이 아니게 됩니다. 테스트에서 정수만 정렬해 보면 차이가 보이지 않으므로, 안정성을 검증하려면 (키, 원래 인덱스) 쌍으로 테스트해야 합니다.

기수 정렬 (Radix Sort)

핵심 아이디어: 자릿수별로 카운팅 정렬을 적용합니다. 정수·문자열 등에 O(n × k)로 동작합니다.

#include <vector>
#include <algorithm>
// LSD (Least Significant Digit) 기수 정렬 - 정수용
void countingSortByDigit(std::vector<int>& a, int exp) {
    const int n = static_cast<int>(a.size());
    std::vector<int> output(n);
    int count[10] = {};
    for (int i = 0; i < n; ++i)
        ++count[(a[i] / exp) % 10];
    for (int i = 1; i < 10; ++i)
        count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; --i) {
        int d = (a[i] / exp) % 10;
        output[count[d] - 1] = a[i];
        --count[d];
    }
    a = std::move(output);
}
void radixSort(std::vector<int>& a) {
    if (a.empty()) return;
    int maxVal = *std::max_element(a.begin(), a.end());
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countingSortByDigit(a, exp);
}
// 사용 예시 (0 이상 정수)
void example_radixsort() {
    std::vector<int> v = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(v);
    // v = {2, 24, 45, 66, 75, 90, 170, 802}
}

countingSortByDigit에서 뒤에서부터(i = n - 1부터) 출력 위치를 채우는 이유도 안정성입니다. LSD 기수 정렬은 낮은 자릿수부터 정렬하면서 이전 패스의 순서가 유지된다는 가정에 의존하므로, 각 패스의 카운팅 정렬이 안정적이지 않으면 전체 결과가 틀립니다. 실무 구현은 10진수 대신 8비트(256 버킷)씩 처리해 int 32비트를 4패스로 끝내는 경우가 많습니다.

하이브리드 정렬 (IntroSort 스타일)

핵심 아이디어: 퀵소트를 기본으로 하되, 재귀 깊이가 깊어지면 힙정렬로 전환하며, 작은 구간은 삽입 정렬로 처리합니다. STL std::sort의 실제 구현과 유사합니다.

#include <vector>
#include <algorithm>
#include <cmath>
// partitionHoare: 위 퀵소트 섹션과 동일
static int partitionHoare(std::vector<int>& a, int lo, int hi) {
    int pivot = a[lo + (hi - lo) / 2];
    int i = lo - 1, j = hi + 1;
    while (true) {
        do ++i; while (a[i] < pivot);
        do --j; while (a[j] > pivot);
        if (i >= j) return j;
        std::swap(a[i], a[j]);
    }
}
void insertionSort(std::vector<int>& a, int lo, int hi) {
    for (int i = lo + 1; i <= hi; ++i) {
        int key = a[i], j = i - 1;
        while (j >= lo && a[j] > key) {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key;
    }
}
void siftDown(std::vector<int>& a, int start, int end) {
    int root = start;
    while (2 * root + 1 <= end) {
        int child = 2 * root + 1;
        if (child + 1 <= end && a[child] < a[child + 1]) ++child;
        if (a[root] >= a[child]) return;
        std::swap(a[root], a[child]);
        root = child;
    }
}
void heapsort(std::vector<int>& a, int lo, int hi) {
    int n = hi - lo + 1;
    for (int start = (n - 2) / 2; start >= 0; --start)
        siftDown(a, lo + start, hi);
    for (int end = hi; end > lo; --end) {
        std::swap(a[lo], a[end]);
        siftDown(a, lo, end - 1);
    }
}
void introsort(std::vector<int>& a, int lo, int hi, int depthLimit) {
    const int threshold = 16;
    if (hi - lo < threshold) {
        insertionSort(a, lo, hi);
        return;
    }
    if (depthLimit == 0) {
        heapsort(a, lo, hi);
        return;
    }
    int p = partitionHoare(a, lo, hi);
    introsort(a, lo, p, depthLimit - 1);
    introsort(a, p + 1, hi, depthLimit - 1);
}
void introsort(std::vector<int>& a) {
    if (a.size() <= 1) return;
    int depthLimit = 2 * static_cast<int>(std::log2(a.size()));
    introsort(a, 0, static_cast<int>(a.size()) - 1, depthLimit);
}

이진 탐색과 lower_bound·파라메트릭 서치

핵심 아이디어: 정렬된 배열에서 중간값과 비교해 범위를 절반씩 좁혀갑니다.

flowchart TD
  A[1,2,5,7,9] --> B{7과 중간값 5 비교}
  B -->|7 > 5| C[오른쪽 절반: 7,9]
  C --> D{7과 7 비교}
  D --> E[찾음!]
#include <vector>
// 값이 있으면 인덱스, 없으면 -1
int binarySearch(const std::vector<int>& a, int target) {
    int lo = 0, hi = static_cast<int>(a.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // 오버플로우 방지
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else                 hi = mid - 1;
    }
    return -1;
}
// 재귀 버전
int binarySearchRecursive(const std::vector<int>& a, int target, int lo, int hi) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target) return binarySearchRecursive(a, target, mid + 1, hi);
    return binarySearchRecursive(a, target, lo, mid - 1);
}

lower_bound, upper_bound, equal_range

lower_bound: >= target인 첫 위치 upper_bound: > target인 첫 위치 equal_range: [lower_bound, upper_bound) 쌍

#include <algorithm>
#include <vector>
void example_bounds() {
    std::vector<int> v = {1, 2, 2, 2, 3, 4, 5};
    // lower_bound: >= 2인 첫 이터레이터
    auto lo = std::lower_bound(v.begin(), v.end(), 2);
    // lo -> v[1] (값 2)
    // upper_bound: > 2인 첫 이터레이터
    auto hi = std::upper_bound(v.begin(), v.end(), 2);
    // hi -> v[4] (값 3)
    // 2의 개수
    int count = std::distance(lo, hi);  // 3
    // equal_range: 한 번에 둘 다
    auto [lb, ub] = std::equal_range(v.begin(), v.end(), 2);
    count = std::distance(lb, ub);  // 3
}

lower_bound는 값이 없어도 “들어갈 위치”를 돌려준다는 점에서 binary_search보다 쓸모가 많습니다. binary_search는 bool만 반환하므로, 존재 여부와 위치가 모두 필요하면 lower_bound 결과를 it != end && *it == target으로 확인하는 편이 한 번의 탐색으로 끝납니다. 연관 컨테이너(std::set, std::map)에는 자유 함수 std::lower_bound가 아니라 멤버 함수 s.lower_bound(x)를 써야 합니다. 자유 함수는 양방향 반복자에서 advance가 선형이라 O(n)이 되기 때문입니다.

범위 쿼리 실전 예제

상황: 정렬된 점수 목록에서 “60점 이상 80점 미만”인 학생 수를 구합니다.

#include <algorithm>
#include <vector>
int countInRange(const std::vector<int>& sorted_scores, int low, int high) {
    // low 이상 high 미만
    auto first = std::lower_bound(sorted_scores.begin(), sorted_scores.end(), low);
    auto last  = std::upper_bound(sorted_scores.begin(), sorted_scores.end(), high - 1);
    return static_cast<int>(std::distance(first, last));
}
// 사용 예시
void example_range_query() {
    std::vector<int> scores = {45, 52, 60, 65, 70, 75, 80, 85, 90};
    int count = countInRange(scores, 60, 80);  // 60~79: 4명 (60, 65, 70, 75)
}

upper_bound(high - 1)은 정수에서만 성립하는 우회입니다. 반열린 구간 [low, high)는 lower_bound(low)와 lower_bound(high)의 차이로 구하는 것이 일반적이고, double이나 문자열 키에도 그대로 쓸 수 있으며 high가 INT_MIN일 때의 언더플로도 없습니다.

상황: “최대/최소를 만족하는 값”을 이진 탐색으로 찾습니다. 예: 정렬된 배열에서 삽입 위치.

#include <vector>
#include <algorithm>
// 정렬된 배열에 target을 삽입할 때 올바른 위치 (중복 시 맨 앞)
size_t insertionPosition(const std::vector<int>& a, int target) {
    return std::lower_bound(a.begin(), a.end(), target) - a.begin();
}
// Parametric: "조건을 만족하는 최소 x" 찾기
// 예: f(x)=true인 최소 x (f는 x에 대해 단조 증가)
template<typename Func>
int binarySearchAnswer(int lo, int hi, Func&& f) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (f(mid)) hi = mid;
        else        lo = mid + 1;
    }
    return lo;
}
// 실전 예: 정렬된 배열에서 "x 이상인 첫 위치" (lower_bound와 동일)
// Parametric으로 "배열 a에서 a[i] >= x인 최소 i" 찾기
int firstNotLessThan(const std::vector<int>& a, int x) {
    return binarySearchAnswer(0, static_cast<int>(a.size()),
        [&](int i) { return a[i] >= x; });
}

커스텀 타입으로 정렬·검색

상황: Person 구조체를 이름·나이로 정렬하며, 특정 이름으로 검색합니다.

#include <algorithm>
#include <vector>
#include <string>
struct Person {
    std::string name;
    int age;
};
// 비교자: 이름 오름차순, 같으면 나이 오름차순
bool comparePerson(const Person& a, const Person& b) {
    if (a.name != b.name) return a.name < b.name;
    return a.age < b.age;
}
// 이름으로 검색할 때: Person과 int 비교가 안 되므로
// 비교자 오버로드 또는 투명 비교자 사용
void exampleCustomType() {
    std::vector<Person> people = {
        {"Alice", 30}, {"Bob", 25}, {"Charlie", 35}
    };
    std::sort(people.begin(), people.end(), comparePerson);
    // "Bob" 이상인 첫 사람 찾기
    Person key = {"Bob", 0};
    auto it = std::lower_bound(people.begin(), people.end(), key,
         [](const Person& a, const Person& b) { return a.name < b.name; });
}

검색용 Person 객체를 만들지 않고 이름 문자열로 바로 찾을 수도 있습니다. lower_bound의 비교자는 (원소, 값) 순서로 호출되므로 [](const Person& p, const std::string& n) { return p.name < n; }처럼 두 타입을 받는 비교자를 넘기면 됩니다. 이때 upper_bound는 인자 순서가 (값, 원소)로 반대라서 같은 람다를 쓰면 컴파일 오류가 납니다. C++20 std::ranges::lower_bound(people, "Bob", {}, &Person::name)처럼 프로젝션을 쓰면 이 비대칭을 신경 쓰지 않아도 됩니다. 또 이름만으로 검색해도 되는 이유는 정렬 기준(이름 → 나이)의 첫 키가 이름이기 때문입니다. 정렬 기준과 다른 필드로 이진 탐색하면 결과가 틀립니다.

무한 루프·정렬 전제 위반·퀵소트 최악 케이스

이진 탐색에서 무한 루프

증상: 프로그램이 종료되지 않습니다. 원인: mid 계산 시 (lo + hi) / 2를 쓰면 lo + hi 오버플로우 가능. 또는 lo = mid로 업데이트하면 lo와 hi가 1 차이일 때 무한 루프.

// ❌ 잘못된 mid 계산 (오버플로우)
int mid = (lo + hi) / 2;
// ✅ 올바른 mid 계산
int mid = lo + (hi - lo) / 2;
// ❌ 무한 루프 가능 (lo=3, hi=4일 때 mid=3, lo=3 유지)
while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (condition) lo = mid;   // hi로 수렴 안 함
    else           hi = mid - 1;
}
// ✅ 올바른 경계 처리
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (condition) hi = mid;   // 또는 lo = mid + 1
    else           lo = mid + 1;
}

정렬되지 않은 배열에 lower_bound 사용

증상: 잘못된 결과 또는 정의되지 않은 동작. 원인: lower_bound, upper_bound, binary_search는 정렬된 범위에서만 동작합니다.

// ❌ 잘못된 사용
std::vector<int> v = {5, 2, 8, 1, 9};
auto it = std::lower_bound(v.begin(), v.end(), 5);  // UB!
// ✅ 올바른 사용
std::sort(v.begin(), v.end());
auto it = std::lower_bound(v.begin(), v.end(), 5);

비교자에서 strict weak ordering 위반

증상: 정렬 결과가 이상하거나 크래시. 원인: a < b와 b < a가 동시에 true이거나, a < a가 true가 되면 안 됩니다. <=를 쓴 비교자는 comp(a, a)가 true라서 이 규칙을 어깁니다.

이 버그가 무서운 이유는 증상이 “결과가 조금 이상함”에 그치지 않는다는 점입니다. libstdc++의 std::sort는 성능을 위해 삽입 정렬 단계에서 경계 검사를 생략하는데(unguarded insertion), 이는 비교자가 규칙을 지킨다는 가정에 기댄 최적화입니다. <= 비교자에 같은 값이 많은 입력을 넣으면 이 루프가 배열 시작을 넘어 읽어 세그폴트가 나기도 합니다. 작은 입력에서는 멀쩡하고 특정 크기(16개 초과) 이상에서만 크래시가 나서, 처음 겪으면 정렬 함수가 아니라 메모리 손상을 의심하게 됩니다. 부동소수점 키에 NaN이 섞여 있을 때도 같은 일이 생깁니다. NaN < x와 x < NaN이 모두 false라서 동치 관계의 추이성이 깨지기 때문입니다. -D_GLIBCXX_DEBUG를 켜면 libstdc++가 일부 비교자 위반을 감지해 알려 줍니다.

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

퀵소트 최악 케이스 (이미 정렬된 데이터)

증상: 정렬된 배열에서 퀵소트가 O(n²)로 매우 느립니다. 원인: 피벗을 항상 첫/끝 원소로 선택하면, 이미 정렬된 데이터에서 한쪽으로만 분할됩니다.

// ❌ 최악: 피벗을 항상 끝으로
int pivot = a[hi];
// ✅ 개선: 중간값 또는 랜덤 피벗
int pivot = a[lo + (hi - lo) / 2];
// 또는
int pivot = a[lo + rand() % (hi - lo + 1)];

lower_bound와 upper_bound 반환값 혼동

증상: “이상”과 “초과”를 잘못 써서 범위가 어긋납니다. 원인: lower_bound는 >=, upper_bound는 >입니다.

// "5 이상 10 미만" 개수
auto lo = std::lower_bound(v.begin(), v.end(), 5);   // >= 5
auto hi = std::upper_bound(v.begin(), v.end(), 9);   // > 9 → 10 미만
int count = std::distance(lo, hi);
// ❌ "10 미만"을 구할 때 upper_bound(10)을 쓰면 10까지 포함됨
// ✅ "10 미만" = lower_bound(10), "10 이하" = upper_bound(10)

기수 정렬에 음수 포함

증상: 음수가 있는 배열을 기수 정렬하면 순서가 잘못됩니다. 원인: 위 LSD 기수 정렬은 0 이상 정수만 가정합니다. 음수는 부호 비트 처리 또는 오프셋이 필요합니다.

// ❌ 음수 포함 시 잘못된 결과
std::vector<int> v = {-5, 3, -2, 0};
radixSort(v);  // 정의되지 않은 동작
// ✅ 해결: 음수는 별도 처리하거나 std::sort 사용
// 또는 2의 보수 오프셋을 적용한 기수 정렬 구현

stable_sort 비용·부분 정렬·메모리 접근

std::sort vs std::stable_sort

상황추천이유
일반 정렬std::sortIntroSort, 캐시 친화적, 빠름
동일 키 순서 유지std::stable_sort병합정렬 기반, 안정
// 안정성이 필요할 때만 stable_sort (보조 버퍼 할당과 병합 비용)
std::stable_sort(people.begin(), people.end(), byName);

“이름으로 정렬하되 같은 이름은 가입일 순”이라는 요구사항은 두 가지로 풀 수 있습니다. 하나는 가입일로 먼저 정렬한 뒤 이름으로 stable_sort하는 다단계 방식이고, 다른 하나는 비교자에 두 키를 모두 넣어(std::tie(a.name, a.joined) < std::tie(b.name, b.joined)) std::sort 한 번으로 끝내는 방식입니다. 두 번째가 보통 빠르고 의도도 명확합니다. stable_sort가 꼭 필요한 경우는 원래 순서 자체가 의미를 갖지만 그 순서를 키로 표현할 수 없을 때, 예를 들어 사용자가 화면에서 이미 정렬해 둔 목록을 다른 열로 다시 정렬할 때입니다.

stable_sort는 추가 메모리 할당에 실패하면 예외를 던지지 않고 제자리 병합으로 넘어가 O(n log² n)이 됩니다. 메모리가 빡빡한 환경에서 갑자기 느려지는 원인이 되기도 합니다.

부분 정렬로 상위 k개만

// 가장 작은 10개만 필요할 때 (기본 비교자 <)
std::partial_sort(v.begin(), v.begin() + 10, v.end());
// v[0..9]만 정렬되며, 나머지는 순서 무관
// 10번째로 작은 값만 필요할 때 (순서 불필요)
std::nth_element(v.begin(), v.begin() + 9, v.end());
// v[9]가 10번째로 작은 값

“상위 10개”가 큰 값 기준이라면 두 함수 모두 마지막 인자로 std::greater<>()를 넘겨야 합니다. 기본 비교자로 호출하면 가장 작은 10개가 나오는데, 예제가 오름차순 데이터로만 테스트되면 이 실수를 놓치기 쉽습니다. partial_sort는 내부적으로 크기 k의 힙을 유지하므로 k가 n에 가까워지면 전체 std::sort보다 느려집니다. k가 크고 순서도 필요하다면 nth_element로 앞쪽 k개를 모은 뒤 그 부분만 std::sort하는 조합이 대개 더 빠릅니다.

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

// 새 원소를 정렬된 벡터에 삽입
void insertSorted(std::vector<int>& v, int x) {
    auto it = std::lower_bound(v.begin(), v.end(), x);
    v.insert(it, x);
}

위치 찾기는 O(log n)이지만 vector::insert가 뒤쪽 원소를 모두 밀어야 하므로 삽입 한 번은 O(n)입니다. 원소를 하나씩 m번 넣으면 O(n·m)이 되므로, 한꺼번에 들어오는 데이터라면 뒤에 모두 붙인 뒤 한 번 정렬하거나 std::inplace_merge로 합치는 편이 낫습니다. 삽입과 조회가 섞여 계속 일어나면 std::set/std::multiset이 맞고, 조회가 압도적으로 많고 삽입이 드물다면 정렬된 vector가 캐시 효율 덕분에 트리보다 빠른 경우가 많습니다. C++23의 std::flat_set이 바로 이 절충을 표준화한 컨테이너입니다.

알고리즘별 성능 경향 (100만 int, 릴리스 빌드 기준으로 생각할 것)

알고리즘경향이유
std::sort기준제자리 분할, 캐시 친화적, 작은 구간 삽입 정렬
std::stable_sort보통 std::sort보다 느림보조 버퍼 할당과 병합 단계의 추가 복사
퀵소트 (중간 피벗, 직접 구현)std::sort와 비슷하거나 느림표준 구현의 피벗 선택·삽입 정렬 전환 같은 세부 최적화가 없음
병합정렬 (직접 구현)std::sort보다 느린 편매 단계 임시 배열로 복사 (아래 5번처럼 tmp를 재사용하면 개선)
기수 정렬 (int)큰 입력에서 비교 정렬보다 빠를 수 있음비교 없이 O(n × 자릿수 패스), 대신 추가 메모리 필요
이진 탐색 100만 번정렬보다 훨씬 가벼움한 번에 O(log n), 다만 배열이 캐시보다 크면 탐색마다 캐시 미스

실제 시간은 CPU와 데이터 분포(이미 정렬됨, 중복 많음)에 따라 크게 달라지므로, 같은 입력을 복사해 각 알고리즘에 넣고 직접 재 보세요.

메모리 접근 최적화

// 병합정렬에서 tmp 벡터를 미리 할당해 재사용
std::vector<int> tmp(a.size());  // 한 번만 할당
mergesort(a, 0, n - 1, tmp);

정렬·검색 유틸리티와 인덱스 정렬

정렬·검색 유틸리티 클래스

#include <vector>
#include <algorithm>
#include <functional>
template<typename T>
class SortedVector {
    std::vector<T> data;
public:
    void insert(const T& x) {
        auto it = std::lower_bound(data.begin(), data.end(), x);
        data.insert(it, x);
    }
    bool contains(const T& x) const {
        return std::binary_search(data.begin(), data.end(), x);
    }
    size_t countInRange(const T& lo, const T& hi) const {
        auto first = std::lower_bound(data.begin(), data.end(), lo);
        auto last  = std::upper_bound(data.begin(), data.end(), hi);
        return std::distance(first, last);
    }
    const std::vector<T>& get() const { return data; }
};

커스텀 비교자 패턴

// 여러 필드로 정렬할 때
struct ComparePerson {
    bool operator()(const Person& a, const Person& b) const {
        if (a.department != b.department) return a.department < b.department;
        if (a.salary != b.salary) return a.salary > b.salary;  // 높은 순
        return a.name < b.name;
    }
};
std::sort(employees.begin(), employees.end(), ComparePerson());

인덱스 정렬 (원본 유지)

#include <numeric>  // std::iota
// 원본은 그대로 두며, 정렬된 순서의 인덱스만 얻기
std::vector<size_t> sortIndices(const std::vector<int>& v) {
    std::vector<size_t> idx(v.size());
    std::iota(idx.begin(), idx.end(), 0);
    std::sort(idx.begin(), idx.end(),
        [&v](size_t a, size_t b) { return v[a] < v[b]; });
    return idx;
}
// 사용: v[idx[i]]가 i번째로 작은 값

에러 처리 및 검증

#include <optional>
std::optional<size_t> safeBinarySearch(const std::vector<int>& a, int target) {
    if (a.empty()) return std::nullopt;
    auto it = std::lower_bound(a.begin(), a.end(), target);
    if (it == a.end() || *it != target) return std::nullopt;
    return std::distance(a.begin(), it);
}

로깅 및 디버깅

#ifdef DEBUG_SORT
#define LOG_SORT(msg) std::cerr << "[SORT] " << msg << "\n"
#else
#define LOG_SORT(msg) ((void)0)
#endif
void quicksortWithLog(std::vector<int>& a, int lo, int hi) {
    LOG_SORT("partition " << lo << ".." << hi);
    // ...
}

정렬·검색 구현 점검 목록

정렬 구현 전

  • 안정 정렬이 필요한지 확인
  • 데이터 특성 (정수/문자열/복합) 확인
  • 부분 정렬로 충분한지 검토

검색 구현 전

  • 범위가 정렬되어 있는지 확인
  • lower_bound vs upper_bound 구분 (이상/초과)
  • 이터레이터와 인덱스 변환 (distance) 확인

퀵소트

  • 피벗 선택 (중간값 또는 랜덤)
  • 재귀 깊이 제한 또는 IntroSort로 전환
  • 작은 구간은 삽입 정렬

이진 탐색

  • mid = lo + (hi - lo) / 2 (오버플로우 방지)
  • 종료 조건 lo <= hi vs lo < hi 구분
  • Parametric Search 시 경계 처리

프로덕션

  • 비교자 strict weak ordering 준수
  • 빈 벡터·범위 검증
  • 필요 시 인덱스 정렬로 원본 보존

정렬·검색 선택 요약

항목설명
std::sort일반 정렬, IntroSort, O(n log n)
std::stable_sort안정 정렬, 병합정렬
퀵소트피벗 분할, 중간값 피벗 권장
병합정렬안정, O(n) 추가 공간
기수 정렬정수/문자열, O(n × k)
lower_bound>= target 첫 위치
upper_bound> target 첫 위치
equal_range[lower, upper) 쌍

핵심 원칙:

  1. 상황에 맞는 정렬·검색 알고리즘 선택
  2. 정렬된 범위에서만 이진 탐색
  3. 비교자 strict weak ordering 준수
  4. 프로덕션에서는 검증·캐싱 고려

자주 묻는 질문 (FAQ)

Q. 음수가 섞인 정수 배열에 기수 정렬을 쓰면 왜 결과가 틀리나요?

A. 일반적인 LSD 기수 정렬은 자릿수나 바이트 값을 버킷 인덱스로 쓰기 때문에 0 이상의 정수만 가정합니다. 음수는 2의 보수 표현 때문에 최상위 비트가 1이 되어 양수보다 큰 값처럼 분류됩니다. 모든 값에 최솟값만큼 오프셋을 더해 양수로 만든 뒤 정렬하거나, 부호 비트를 뒤집어서 처리해야 합니다.

Q. lower_bound와 upper_bound는 무엇이 다른가요?

A. lower_bound는 target 이상인 첫 위치, upper_bound는 target보다 큰 첫 위치를 반환합니다. 중복이 있는 정렬 배열에서 두 반복자의 차이가 target의 개수이고, equal_range는 이 두 위치를 한 번에 쌍으로 돌려줍니다. 모두 정렬된 범위에서 O(log n)입니다.

Q. std::execution::par로 병렬 정렬하면 항상 빨라지나요?

A. 아닙니다. 데이터가 작으면 스레드를 나누는 비용이 더 크고, 정렬은 메모리 대역폭을 많이 쓰기 때문에 코어 수만큼 빨라지지 않습니다. GCC(libstdc++)에서는 TBB를 링크하지 않으면 병렬 정책을 줘도 순차로 실행되고, 링크를 빠뜨리면 undefined reference to tbb::... 오류가 납니다. 비교자가 공유 상태를 수정하면 데이터 경쟁이 되므로, 병렬 정렬의 비교자는 부작용이 없어야 합니다.

표준 라이브러리 std::sort·lower_bound에서 출발하되, 비교자 규칙과 정렬-검색 비교자 일치, 반열린 구간 경계를 지키는 것이 대부분의 버그를 막습니다.

부록: 정렬·검색 복잡도 요약

알고리즘평균최악공간안정
퀵소트O(n log n)O(n²)O(log n)❌
병합정렬O(n log n)O(n log n)O(n)✅
기수 정렬O(n×k)O(n×k)O(n+k)✅
삽입 정렬O(n²)O(n²)O(1)✅
이진 탐색O(log n)O(log n)O(1)-
lower_boundO(log n)O(log n)O(1)-

참고 자료

같이 보면 좋은 글