pkglog

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

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

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

정렬 알고리즘 선택은 데이터 크기와 “무엇이 필요한가”에 따라 갈립니다. 수십만 건의 로그를 타임스탬프 기준으로 정렬할 때 버블·선택 정렬처럼 O(n²)인 방법을 쓰면 비교 횟수가 수백억 번 수준이 되어 실용적이지 않습니다. std::sort는 O(n log n)이고, 같은 타임스탬프를 가진 로그의 원래 순서까지 유지해야 한다면 std::stable_sort를 씁니다.

100만 명의 점수 중 상위 10명만 필요하다면 전체를 정렬할 이유가 없습니다. std::partial_sort는 O(n log k)로 앞쪽 k개만 정렬하고, std::nth_element는 평균 O(n)에 k번째 경계만 맞춰 주므로 그 뒤 앞부분만 정렬해도 됩니다.

이미 대부분 정렬된 데이터에 원소 몇 개가 추가된 경우, 삽입 정렬은 O(n)에 가깝게 동작합니다. std::sort의 구현들은 정렬된 입력에서 O(n²)로 무너지지 않도록 피벗을 고르지만, 거의 정렬된 입력을 선형 시간에 끝내는 것은 pdqsort 계열처럼 패턴 감지를 하는 구현에 한정됩니다.

이름으로 1차 정렬하고 같은 이름 안에서 점수로 2차 정렬해야 할 때, 불안정 정렬을 두 번 적용하면 첫 번째 정렬의 순서가 깨집니다. 2차 키까지 포함한 비교자 하나로 한 번에 정렬하거나, 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(n²)O(1)O
선택 정렬O(n²)O(n²)O(1)X
삽입 정렬O(n²)O(n²)O(1)O
병합 정렬O(n log n)O(n log n)O(n)O
퀵 정렬O(n log n)O(n²)O(log n) (작은 쪽만 재귀할 때)X
힙 정렬O(n log n)O(n log n)O(1)X
std::sort (인트로소트)O(n log n)O(n log n)O(log n)X

인트로소트(Introsort)란?

libstdc++와 MSVC STL의 std::sort가 사용하는 인트로소트는 퀵소트, 힙소트, 삽입정렬을 섞은 알고리즘입니다. 기본적으로 퀵소트로 분할하다가 재귀 깊이가 약 2·log₂n을 넘으면 그 구간을 힙소트로 정렬해 최악 O(n²)를 막고, 구간 크기가 작아지면(libstdc++는 16, MSVC는 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는 인트로소트를 바탕으로 몇 가지를 더한 알고리즘입니다. 파티션 후 교환이 거의 일어나지 않았다면 이미 정렬된 구간일 가능성이 높다고 보고 횟수를 제한한 삽입정렬을 시도해, 정렬된 입력을 선형 시간에 처리합니다. 피벗과 같은 값이 많으면 그 값들의 구간을 한 번에 떼어 내서, 값 종류가 적은 입력을 빨리 끝냅니다. 비교 결과를 오프셋 버퍼에 모았다가 한꺼번에 교환하는 분기 없는 파티션(BlockQuicksort)으로 무작위 데이터에서 분기 예측 실패를 줄이고, 파티션이 계속 한쪽으로 쏠리면 원소를 섞어 패턴을 깨다가 그래도 안 되면 힙소트로 넘어갑니다.

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

알고리즘 선택 가이드

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

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

아래 O(n²) 알고리즘들을 프로덕션에서 직접 쓸 일은 거의 없지만, 구현해 보면 “안정성은 어디서 생기고 어디서 깨지는가”를 손으로 확인할 수 있습니다. 버블·삽입 정렬은 인접 원소만 바꾸고 같은 값은 건너뛰지 않으므로 안정적이고, 선택 정렬은 멀리 떨어진 원소와 교환하기 때문에 같은 값의 순서가 뒤집힐 수 있습니다. 아래 코드에서 if (n < 2) return;이 빠지면 안 되는 이유도 알아 둘 만합니다. n이 부호 없는 size_t라서 빈 벡터에서 n - 1이 언더플로해 거대한 수가 되고, 루프가 범위 밖을 읽게 됩니다.

버블 정렬 (Bubble Sort)

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

#include <vector>
#include <utility>
// 버블 정렬: O(n²), 안정 정렬, 추가 메모리 없음
void bubble_sort(std::vector<int>& arr) {
    const size_t n = arr.size();
    if (n < 2) return;  // size_t 언더플로 방지
    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회로 적어서, 쓰기 비용이 큰 환경에서 의미가 있음
void selection_sort(std::vector<int>& arr) {
    const size_t n = arr.size();
    if (n < 2) return;
    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)

각 원소를 이미 정렬된 앞부분의 올바른 위치에 삽입합니다. 원소를 옮기는 횟수가 역전 쌍(inversion)의 개수와 같으므로, 거의 정렬된 데이터에서는 빠르고 역순 데이터에서 가장 느립니다.

#include <vector>
// 삽입 정렬: 평균 O(n²), 거의 정렬된 입력에서 O(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)이지만, 병합에 O(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이 됩니다. 스택 사용량이 입력 크기에 비례하므로, 기본 스택 크기(리눅스는 보통 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>
#include <utility>
// 0-based 힙의 자식 인덱스
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();
    if (n < 2) return;  // 아래 n - 1이 언더플로하지 않도록
    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억 칸(약 8GB)짜리 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 <cstddef>
#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와 가장 큰 차이입니다. 그래서 “대소문자를 무시한 비교”처럼 키로 표현하기 어려운 순서에는 쓸 수 없고, 원소 수가 적으면 버킷을 세는 고정 비용 때문에 이점이 없습니다(ska_sort도 작은 구간은 내부적으로 비교 정렬로 넘깁니다). 이득의 크기는 키 분포와 원소 크기에 따라 크게 달라지므로, 도입하기 전에 실제 데이터로 측정해 보아야 합니다.

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

std::sort

같은 값의 순서를 보장하지 않는 불안정 정렬로, 특별한 요구가 없으면 기본 선택입니다.

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
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) 크기의 임시 버퍼를 할당해 O(n log n)에 정렬합니다. 버퍼를 할당하지 못하면 추가 메모리 없이 O(n log² n)으로 동작하는 경로로 넘어갑니다.

#include <algorithm>
#include <string>
#include <vector>
struct LogEntry {
    int timestamp;
    int level;
    std::string msg;
};
void sort_logs(std::vector<LogEntry>& logs) {
    // timestamp로 정렬, 같은 timestamp끼리는 입력 순서 유지
    std::stable_sort(logs.begin(), logs.end(),
        [](const LogEntry& a, const LogEntry& b) {
            return a.timestamp < b.timestamp;
        });
}

std::partial_sort

앞쪽 k개 자리에 가장 작은(비교자 기준으로 앞서는) 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번째 위치에 “정렬했다면 그 자리에 올 원소”를 두고, 그 앞에는 그보다 크지 않은 원소, 뒤에는 그보다 작지 않은 원소를 모읍니다. 앞뒤 구간 안의 순서는 보장하지 않으며, 평균 O(n)입니다.

상위 k개를 정렬된 순서로 보여 줘야 한다면 partial_sort, 경계로 나누기만 하면 된다면 nth_element가 맞습니다. partial_sort는 내부적으로 크기 k의 힙을 쓰므로 k가 n에 가까워지면 전체 sort보다 느려질 수 있고, 이때는 nth_element로 나눈 뒤 앞부분만 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 <iostream>
struct LogEntry {
    std::string timestamp;  // "2026-05-02T14:30:00"
    int level;
    std::string message;
};
void sort_logs_by_time(std::vector<LogEntry>& logs) {
    // 같은 시각의 로그는 입력 순서를 유지
    std::stable_sort(logs.begin(), logs.end(),
        [](const LogEntry& a, const LogEntry& b) {
            return 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;
}

ISO 8601 문자열을 그대로 비교해도 되는 것은 모든 값이 같은 형식(자릿수, 구분자)과 같은 시간대일 때뿐입니다. +09:00과 Z가 섞여 있거나 밀리초 유무가 다르면 문자열 순서와 시간 순서가 어긋나므로, 그때는 먼저 std::chrono 시각이나 정수 타임스탬프로 변환한 값을 키로 써야 합니다.

역순 정렬과 범위 지정

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

구조체 배열 정렬 (C++20 프로젝션과 멤버 포인터)

C++20의 std::ranges::sort는 비교자와 별도로 프로젝션을 받으므로, 멤버 포인터만 넘겨 “이 필드 기준으로 정렬”을 표현할 수 있습니다.

#include <algorithm>
#include <functional>
#include <vector>
#include <string>
#include <iostream>
struct Product {
    int id;
    std::string name;
    double price;
};
int main() {
    std::vector<Product> products = {
        {3, "Keyboard", 89000},
        {1, "Mouse", 35000},
        {2, "Monitor", 250000}
    };
    // name 내림차순: 비교자 std::ranges::greater, 프로젝션 &Product::name
    std::ranges::sort(products, std::ranges::greater{}, &Product::name);
    // price 오름차순: 비교자는 기본값 std::ranges::less, 프로젝션 &Product::price
    std::ranges::sort(products, {}, &Product::price);
    for (const auto& p : products) {
        std::cout << p.name << ": " << p.price << "\n";
    }
    return 0;
}

정렬 함수 비교 측정 코드

아래 코드는 같은 무작위 입력에 대해 세 함수의 실행 시간을 재는 뼈대입니다. 결과는 CPU, 컴파일러, 최적화 옵션, 데이터 분포에 따라 달라지므로 실제 환경에서 -O2 이상으로 직접 돌려 보아야 의미가 있습니다.

#include <algorithm>
#include <vector>
#include <chrono>
#include <random>
#include <iostream>
template<typename Func>
double measure_ms(Func&& f) {
    auto start = std::chrono::steady_clock::now();
    f();
    auto end = std::chrono::steady_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";
}
int main() { run_benchmark(); }

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

비교자에서 strict weak ordering 위반

std::sort가 크래시하거나 끝나지 않는다면 가장 먼저 비교자를 의심해야 합니다. 비교자는 strict weak ordering을 만족해야 합니다. comp(a, a)는 항상 false여야 하고, comp(a, b)가 true면 comp(b, a)는 false여야 하며, 추이성(a<b, b<c이면 a<c)과 “비교 불가능(둘 다 false)” 관계의 추이성도 지켜야 합니다.

// ❌ 잘못된 비교자
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; });

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

반복자 범위 잘못 지정

STL 알고리즘은 [begin, end) 반개구간을 받습니다. end()는 마지막 원소 다음 위치이므로 여기에 1을 더하면 범위 밖 접근입니다. 반면 빈 범위는 안전하게 처리됩니다.

// ❌ end 다음까지 포함 → 범위 밖 접근(미정의 동작)
std::sort(v.begin(), v.end() + 1);
// ✅ 빈 벡터에 sort는 아무 일도 하지 않음
std::vector<int> empty;
std::sort(empty.begin(), empty.end());

정렬 중 컨테이너 수정

비교자 안에서 정렬 중인 컨테이너를 수정하면 반복자가 무효화되어 미정의 동작이 됩니다.

// ❌ 정렬 중에 벡터에 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 사용

키별로 정렬을 두 번 나눠 하면서 불안정한 sort를 쓰면, 두 번째 정렬이 첫 번째 정렬의 순서를 깨뜨립니다.

// ❌ 이름으로 정렬한 뒤 점수로 정렬 → 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번 정렬 (2차 키 먼저, 1차 키 나중)
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은 어떤 값과 비교해도 < 결과가 false → strict weak ordering 위반, 미정의 동작
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에서는 비교자가 던진 예외가 호출자에게 그대로 전파되지만, 그 시점의 범위는 원소들이 섞인 “유효하지만 순서를 알 수 없는” 상태로 남습니다. 병렬 실행 정책을 쓴 경우에는 예외가 전파되지 않고 std::terminate가 호출됩니다. 그래서 검증은 정렬 전에 끝내고, 비교자는 예외를 던지지 않는 단순한 비교로 유지하는 편이 안전합니다.

// ❌ 비교 도중 검증: 예외가 나면 범위가 반쯤 섞인 채로 남음
std::sort(v.begin(), v.end(), [](int a, int b) {
    if (a < 0 || b < 0) throw std::runtime_error("negative");
    return a < b;
});
// ✅ 검증은 먼저, 비교자는 순수한 비교만
if (std::any_of(v.begin(), v.end(), [](int x) { return x < 0; })) {
    throw std::runtime_error("negative");
}
std::sort(v.begin(), v.end());

비교 비용·이동 비용·메모리

비교 비용이 클 때

문자열 정규화나 계산이 필요한 키처럼 비교 한 번이 비싸다면, 비교할 때마다 키를 다시 계산하지 말고 키를 미리 한 번씩 계산해 (키, 인덱스) 쌍을 정렬하는 편이 낫습니다. 정렬은 비교를 O(n log n)번 하므로 키 계산도 그만큼 반복되지만, 미리 계산하면 n번으로 줄어듭니다. 키가 정수라면 앞에서 본 기수 정렬도 선택지입니다.

이동 비용이 클 때

std::sort는 원소를 swap과 이동으로 재배치하므로, 원소 타입의 이동 연산이 싸야 빠릅니다. std::string이나 std::vector처럼 이동이 포인터 몇 개 복사로 끝나는 타입은 문제없지만, 큰 배열을 값으로 품은 구조체는 이동이 곧 복사입니다. 이런 경우 인덱스나 포인터를 정렬하고 나중에 한 번만 재배치합니다. 비교자는 const auto&로 받아 비교할 때마다 복사가 일어나지 않게 합니다.

std::sort(items.begin(), items.end(),
    [](const auto& a, const auto& b) {
        return a.key() < b.key();
    });

메모리 제약

std::stable_sort는 임시 버퍼를 할당합니다. 메모리가 극히 제한적이면 std::sort에 2차 키까지 포함한 비교자를 써서 안정 정렬 없이 순서를 결정합니다.

정렬된 두 시퀀스 병합

이미 정렬된 두 벡터를 합칠 때는 std::merge가 O(n + m)으로, 이어 붙인 뒤 다시 정렬하는 것보다 효율적입니다.

#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는 O(n)에 정렬 여부를 확인합니다. 대부분 이미 정렬된 상태로 들어오는 데이터라면 정렬을 건너뛸 수 있습니다.

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

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

정렬 가능한 타입 설계

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

operator<를 하나의 필드만으로 정의하면 그 필드가 같은 두 객체는 “같은 것”으로 취급됩니다. 정렬에는 문제가 없지만, 같은 타입을 std::set 키로 쓰면 created_at이 같은 주문이 중복으로 간주되어 삽입되지 않는다는 점을 기억해 두십시오.

병렬 정렬 (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는 Windows 스레드 풀 위에 구현되어 추가 라이브러리가 필요 없고, Clang의 libc++는 버전에 따라 지원 수준이 달라 확인이 필요합니다.

여러 스레드가 비교자를 동시에 호출하므로, 비교 횟수를 세는 전역 카운터처럼 공유 상태를 건드리는 비교자는 데이터 경쟁으로 미정의 동작이 됩니다. 또 병렬 정책으로 실행되는 알고리즘 안에서 예외가 빠져나오면 호출자에게 전달되지 않고 std::terminate가 호출됩니다.

작은 데이터에서는 작업 분배와 병합 비용 때문에 오히려 손해일 수 있습니다. 이득이 생기는 크기는 CPU 코어 수, 원소 타입, 비교자 비용에 따라 크게 달라지므로 직접 측정해서 정해야 합니다. std::stable_sort에도 병렬 정책 오버로드가 있습니다.

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

새 원소를 삽입할 때마다 정렬된 상태를 유지하려면 lower_bound로 위치를 찾아 삽입합니다. 위치 탐색은 O(log n)이지만 vector::insert가 뒤쪽 원소를 밀어내므로 삽입마다 O(n)입니다. 삽입이 잦다면 std::multiset이나 모아서 한 번에 정렬하는 방식을 검토합니다.

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

런타임에 정렬 기준 선택

정렬 기준을 런타임에 고를 때는 기준마다 람다를 두고 switch로 분기하면 됩니다. 각 분기의 람다 타입이 달라 컴파일러가 비교를 인라인할 수 있으므로, std::function 하나에 담아 넘기는 것보다 보통 유리합니다.

#include <algorithm>
#include <vector>
#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;
    }
}

이진 탐색과 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)는 [lo, hi)에서 false...false true...true 형태여야 함 (단조)
// 모두 false면 hi를 반환
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;
}
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, std::string{"Bob"}, {}, &Person::name)처럼 프로젝션을 쓰면 이 비대칭을 신경 쓰지 않아도 됩니다. 또 이름만으로 검색해도 되는 이유는 정렬 기준(이름 → 나이)의 첫 키가 이름이기 때문입니다. 정렬 기준과 다른 필드로 이진 탐색하면 결과가 틀립니다.

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

이진 탐색에서 무한 루프와 오버플로

이진 탐색이 끝나지 않는 가장 흔한 원인은 경계 갱신입니다. mid를 내림으로 계산하면서 lo = mid로 갱신하면, lo와 hi가 1 차이일 때 mid == lo가 되어 범위가 줄지 않습니다. 또 (lo + hi) / 2는 두 인덱스가 크면 lo + hi가 int 범위를 넘을 수 있으므로 lo + (hi - lo) / 2로 계산합니다.

// 오버플로 가능
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 - lo) / 2;
    if (condition) lo = mid;
    else           hi = mid - 1;
}
// 내림 mid와 짝이 맞는 갱신: hi = mid 또는 lo = mid + 1
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (condition) hi = mid;
    else           lo = mid + 1;
}

lo = mid 형태가 꼭 필요하다면 mid = lo + (hi - lo + 1) / 2처럼 올림으로 계산해야 범위가 줄어듭니다.

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

lower_bound, upper_bound, binary_search는 범위가 검색 값을 기준으로 분할(정렬)되어 있다는 전제 조건을 가집니다. 이 조건을 어기면 표준상 미정의 동작이고, 실제로는 예외 없이 엉뚱한 위치를 돌려줍니다.

std::vector<int> v = {5, 2, 8, 1, 9};
auto bad = std::lower_bound(v.begin(), v.end(), 5);  // 전제 조건 위반
std::sort(v.begin(), v.end());
auto it = std::lower_bound(v.begin(), v.end(), 5);   // 올바른 사용

디버그 빌드에서는 libstdc++의 -D_GLIBCXX_DEBUG나 MSVC의 디버그 반복자가 이런 위반 일부를 검사해 줍니다.

비교자에서 strict weak ordering 위반

<=처럼 comp(a, a)가 true가 되는 비교자나 NaN이 섞인 부동소수점 키는 정렬 결과를 망가뜨리는 데 그치지 않고, libstdc++의 경계 검사 없는 삽입 정렬 단계에서 배열 밖을 읽어 크래시를 낼 수 있습니다. 증상과 디버그 모드로 잡는 방법, NaN 처리 비교자는 C++ 정렬 알고리즘 구현과 비교에서 자세히 다룹니다. 검색 쪽에서 기억할 점은 이진 탐색에도 정렬과 같은 비교자를 넘겨야 한다는 것입니다.

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

피벗을 항상 첫 원소나 끝 원소로 고르면, 이미 정렬된 데이터에서 매번 한쪽으로만 분할되어 O(n²)이 되고 재귀 깊이도 n이 되어 스택 오버플로까지 날 수 있습니다. 중간 위치나 무작위 위치, 또는 처음·중간·끝 세 값의 중앙값을 피벗으로 고릅니다.

int pivot = a[hi];                         // 정렬된 입력에서 최악
int pivot = a[lo + (hi - lo) / 2];         // 중간 위치
int pivot = a[lo + rand() % (hi - lo + 1)]; // 무작위 위치

중간 위치 피벗도 특정 패턴(일명 median-of-3 killer)에서는 여전히 O(n²)이 될 수 있습니다. 최악을 보장하려면 앞의 IntroSort처럼 재귀 깊이를 제한하고 힙정렬로 넘어가야 하며, 표준 std::sort가 하는 일이 바로 이것입니다.

lower_bound와 upper_bound 반환값 혼동

“이상”과 “초과”를 바꿔 써서 범위가 하나씩 어긋나는 실수입니다. lower_bound는 >=, upper_bound는 >이므로, 반열린 구간 [5, 10)은 lower_bound(5)부터 lower_bound(10)까지, 닫힌 구간 [5, 10]은 lower_bound(5)부터 upper_bound(10)까지입니다.

// "5 이상 10 미만" 개수
auto first = std::lower_bound(v.begin(), v.end(), 5);   // >= 5
auto last  = std::lower_bound(v.begin(), v.end(), 10);  // >= 10, 즉 10 미만의 끝
auto count = std::distance(first, last);
// upper_bound(v.begin(), v.end(), 10)을 쓰면 10까지 포함됨

기수 정렬에 음수 포함

앞의 LSD 기수 정렬은 0 이상의 정수만 가정합니다. 음수가 들어오면 (a[i] / exp) % 10이 음수가 되어 count[-5]처럼 배열 밖을 접근하므로, 결과가 틀리는 정도가 아니라 미정의 동작입니다. 바이트 단위로 처리하는 구현에서는 음수의 최상위 비트가 1이라 양수보다 큰 값으로 분류됩니다. 모든 값에서 최솟값을 빼서 0 이상으로 만든 뒤 정렬하거나, 부호 있는 정수를 uint32_t로 바꿀 때 부호 비트를 뒤집어(x ^ 0x80000000u) 순서를 보존하는 방법을 씁니다.

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

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

#include <algorithm>
#include <iterator>
#include <vector>
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);
    }
    // 닫힌 구간 [lo, hi]에 속한 원소 수
    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 static_cast<size_t>(std::distance(first, last));
    }
    const std::vector<T>& get() const { return data; }
};

삽입이 O(n)이라는 앞의 설명이 그대로 적용되므로, 이 클래스는 조회가 대부분이고 삽입이 드문 경우에 맞습니다.

커스텀 비교자 패턴

여러 필드로 정렬할 때는 필드 순서대로 비교하고, 앞 필드가 같을 때만 다음 필드로 넘어갑니다. 필드마다 방향이 다를 수 있습니다.

struct Employee {
    std::string department;
    int salary;
    std::string name;
};
struct CompareEmployee {
    bool operator()(const Employee& a, const Employee& 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(), CompareEmployee());

인덱스 정렬 (원본 유지)

#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번째로 작은 값

원소가 크거나 여러 배열을 같은 순서로 다시 배치해야 할 때, 원본은 건드리지 않고 순서만 얻을 수 있습니다. 같은 값의 인덱스 순서까지 원래대로 두려면 std::stable_sort를 씁니다.

찾지 못한 경우를 타입으로 표현

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

-1 같은 특수 값 대신 std::optional을 돌려주면, 호출자가 “찾지 못함”을 검사하지 않고 인덱스로 쓰는 실수를 컴파일러가 막아 줍니다.

퀵소트·병합 정렬 동작 시각화

퀵소트 파티션 과정

앞의 Lomuto 파티션을 [5, 2, 8, 1, 9, 3, 7]에 적용하면, 피벗 7보다 작거나 같은 원소가 앞으로 모이고 피벗이 인덱스 4에 놓입니다.

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[8]
        B7[9]
    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

같이 보면 좋은 글