C++ 정렬·검색 완벽 가이드 | 퀵소트·병합정렬·이진탐색·STL [실전]

· 35분 읽기 · 수정 고급 실습
C++ 정렬·검색 완벽 가이드 | 퀵소트·병합정렬·이진탐색·STL [실전]

이 글의 핵심

정렬(퀵소트, 병합정렬, 기수정렬)과 검색(이진탐색, lower_bound, upper_bound)을 C++로 구현. 문제 시나리오, 완전한 코드, 흔한 실수, 성능 팁, 프로덕션 패턴.

들어가며: “100만 건 정렬이 30초나 걸려요”

정렬·검색 선택의 함정

대용량 데이터를 정렬하거나 검색할 때, 잘못된 알고리즘을 쓰면 100만 건에서 수십 초가 걸립니다. 비유하면 “버블 정렬로 일일이 비교하는 것”과 “퀵소트·병합정렬로 O(n log n)에 처리하는 것”의 차이입니다.

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

이 글에서는 실제로 겪는 문제 시나리오부터 시작해, 정렬·검색의 완전한 C++ 구현, 자주 하는 실수, 성능 최적화 팁, 프로덕션 패턴까지 단계별로 다룹니다.

이 글을 읽으면:

  • 상황에 맞는 정렬·검색 알고리즘을 선택할 수 있습니다.
  • 퀵소트, 병합정렬, 기수정렬, 이진탐색을 직접 구현할 수 있습니다.
  • STL std::sort, lower_bound, upper_bound를 올바르게 활용할 수 있습니다.

요구 환경: C++17 이상

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

목차

  1. 문제 시나리오
  2. STL 정렬·검색 개요
  3. 완전한 정렬 예제
  4. 완전한 검색 예제
  5. 자주 발생하는 에러와 해결법
  6. 성능 최적화 팁
  7. 프로덕션 패턴
  8. 구현 체크리스트

1. 문제 시나리오

시나리오 1: 대용량 로그 파일 정렬

상황: 100만 건의 로그를 타임스탬프 기준으로 정렬해야 합니다.

잘못된 접근: 버블 정렬이나 선택 정렬을 쓰면 O(n²)로 수십 초가 걸립니다.

해결: std::sort 또는 퀵소트/병합정렬 O(n log n) 사용. 100만 건도 0.1초 내외.

시나리오 2: 정렬된 배열에서 범위 검색

상황: 이미 정렬된 사용자 ID 목록에서 “1000 이상 2000 미만”인 사용자 수를 찾아야 합니다.

잘못된 접근: 순차 탐색 O(n)으로 전체를 훑습니다.

해결: lower_bound와 upper_bound로 O(log n)에 범위 경계를 찾고, upper_bound - lower_bound로 개수 계산.

시나리오 3: 안정 정렬이 필요한 경우

상황: 이름으로 정렬한 뒤, 같은 이름 내에서는 가입일 순으로 유지해야 합니다.

잘못된 접근: std::sort는 불안정 정렬이라 같은 키의 상대 순서가 바뀔 수 있습니다.

해결: std::stable_sort 또는 병합정렬 사용. 동일 키의 원래 순서를 유지합니다.

시나리오 4: 정수만 있는 데이터 (기수 정렬)

상황: 0~999999 범위의 정수 100만 개를 정렬해야 합니다.

잘못된 접근: 비교 기반 정렬은 O(n log n) 하한이 있습니다.

해결: 기수 정렬 O(n × k)로, k가 작으면 비교 정렬보다 빠를 수 있습니다. 특히 메모리 접근 패턴이 캐시 친화적입니다.

시나리오 5: 부분 정렬만 필요한 경우

상황: 상위 10명만 필요할 때 100만 명 전체를 정렬하는 것은 낭비입니다.

잘못된 접근: std::sort로 전체 정렬 후 앞 10개만 사용.

해결: std::partial_sort 또는 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)

2. 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(),
     {
        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와 같은 값들

3. 완전한 정렬 예제

3.1 퀵소트 (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}
}

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

3.3 기수 정렬 (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}
}

3.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);
}

4. 완전한 검색 예제

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

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

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

4.3 범위 쿼리 실전 예제

상황: 정렬된 점수 목록에서 “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: 5명
}

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

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

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

상황: 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,
         { return a.name < b.name; });
}

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

문제 1: 이진 탐색에서 무한 루프

증상: 프로그램이 종료되지 않습니다.

원인: 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;
}

문제 2: 정렬되지 않은 배열에 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);

문제 3: 비교자에서 strict weak ordering 위반

증상: 정렬 결과가 이상하거나 크래시.

원인: a < b와 b < a가 동시에 true이거나, a < a가 true가 되면 안 됩니다.

// ❌ 잘못된 비교자
std::sort(v.begin(), v.end(),  {
    return a <= b;  // a==b일 때 true 반환 → strict weak ordering 위반
});

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

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

증상: 정렬된 배열에서 퀵소트가 O(n²)로 매우 느립니다.

원인: 피벗을 항상 첫/끝 원소로 선택하면, 이미 정렬된 데이터에서 한쪽으로만 분할됩니다.

// ❌ 최악: 피벗을 항상 끝으로
int pivot = a[hi];

// ✅ 개선: 중간값 또는 랜덤 피벗
int pivot = a[lo + (hi - lo) / 2];
// 또는
int pivot = a[lo + rand() % (hi - lo + 1)];

문제 5: 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 이하" = upper_bound(10) - begin (10 초과 첫 위치가 "10 이하"의 끝)

문제 6: 기수 정렬에 음수 포함

증상: 음수가 있는 배열을 기수 정렬하면 순서가 잘못됩니다.

원인: 위 LSD 기수 정렬은 0 이상 정수만 가정합니다. 음수는 부호 비트 처리 또는 오프셋이 필요합니다.

// ❌ 음수 포함 시 잘못된 결과
std::vector<int> v = {-5, 3, -2, 0};
radixSort(v);  // 정의되지 않은 동작

// ✅ 해결: 음수는 별도 처리하거나 std::sort 사용
// 또는 2의 보수 오프셋을 적용한 기수 정렬 구현

6. 성능 최적화 팁

1. std::sort vs std::stable_sort

상황추천이유
일반 정렬std::sortIntroSort, 캐시 친화적, 빠름
동일 키 순서 유지std::stable_sort병합정렬 기반, 안정
// 안정성이 필요할 때만 stable_sort (일반적으로 1.5~2배 느림)
std::stable_sort(people.begin(), people.end(), byName);

2. 부분 정렬로 상위 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번째로 큰 값

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

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

4. 벤치마크 참고 (100만 int, 릴리스 빌드)

알고리즘시간 (대략)
std::sort~80ms
std::stable_sort~120ms
퀵소트 (중간 피벗)~90ms
병합정렬~100ms
기수 정렬 (int)~60ms
이진 탐색 100만 번~20ms

5. 메모리 접근 최적화

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

7. 프로덕션 패턴

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

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

2. 커스텀 비교자 패턴

// 여러 필드로 정렬할 때
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());

3. 인덱스 정렬 (원본 유지)

// 원본은 그대로 두고, 정렬된 순서의 인덱스만 얻기
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번째로 작은 값

4. 에러 처리 및 검증

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

5. 로깅 및 디버깅

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

8. 구현 체크리스트

정렬 구현 전

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

검색 구현 전

  • 범위가 정렬되어 있는지 확인
  • 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. 대용량 데이터 정렬, 로그·이벤트 검색, 범위 쿼리(점수대, 가격대), 순위·백분위 계산, 안정 정렬이 필요한 데이터 처리 등에 활용합니다.

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

A. STL 컨테이너(vector, iterator), 비교자(comparator) 기초, 재귀·분할정복 개념을 먼저 익히면 좋습니다.

Q. 더 깊이 공부하려면?

A. cppreference의 std::sort, std::lower_bound 문서, LeetCode 정렬·이진탐색 유형, 《알고리즘 설계》 정렬 챕터를 참고하세요.

한 줄 요약: 퀵소트·병합정렬·기수정렬과 이진탐색·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)-

참고 자료

관련 글

  • C++ 정렬 알고리즘 완벽 가이드 | sort·stable_sort·직접 구현 [#54-7]
  • C++ Algorithm Sort |
  • C++ Algorithm Search |
  • C++ 알고리즘 |
... 996 lines not shown ... Token usage: 63706/1000000; 936294 remaining Start-Sleep -Seconds 3