정렬 알고리즘

실무에서는 std::sort

기본 사용

#include <algorithm>
std::sort(v.begin(), v.end());

• 실무에서는 대부분 std::sort로 충분합니다.
• 내부는 보통 Introsort(Quick + Heap + Insertion 하이브리드) 계열로 매우 최적화되어 있습니다.

사용자 기준 정렬 (비교 함수)

std::sort(players.begin(), players.end(),
    [](const Player& a, const Player& b) {
        if (a.level != b.level) return a.level > b.level; // 레벨 내림차순
        return a.id < b.id;                               // id 오름차순
    });

Comparator 규칙 (중요)

• 비교 함수는 "lhs가 rhs보다 앞에 와야 하면 true"를 반환해야 합니다.
• 일관성이 깨지면(모순된 비교) 정렬 결과가 비정상적이거나 UB로 이어질 수 있습니다.
• 같은 값끼리는 comp(a, b) == false 그리고 comp(b, a) == false가 되어야 합니다.

stable_sort가 필요한 경우

std::stable_sort(v.begin(), v.end(), comp);

• 동등 키의 기존 상대 순서를 보존해야 할 때 사용합니다.
• 예: "직급으로 정렬하되, 같은 직급은 입사 순서 유지"

컨테이너 제약

• std::sort는 Random Access Iterator가 필요합니다.
• vector, deque는 가능.
• list는 불가 -> list.sort() 멤버 함수 사용.

---

버블 정렬 (Bubble Sort)

원리

• 인접한 두 요소를 비교해 자리 바꿈. 한 턴마다 가장 큰 값이 오른쪽으로.
• "거품"이 올라가는 것처럼 보여서 버블 정렬.

코드

void BubbleSort(std::vector<int>& v) {
    const int n = v.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (v[j] > v[j + 1]) {
                std::swap(v[j], v[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 이미 정렬됨
    }
}

시간 복잡도

• 평균/최악 O(N²), 이미 정렬된 경우(최적화 시) O(N).

---

선택 정렬 (Selection Sort)

원리

• 매 턴마다 "가장 작은 값"을 찾아 앞 자리에 배치.

코드

void SelectionSort(std::vector<int>& v) {
    const int n = v.size();
    for (int i = 0; i < n - 1; i++) {
        int bestIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (v[j] < v[bestIdx]) bestIdx = j;
        }
        std::swap(v[i], v[bestIdx]);
    }
}

시간 복잡도

• O(N²).
• swap 횟수는 상대적으로 적지만 비교 횟수는 많습니다.

---

힙 정렬 (Heap Sort)

원리

• 힙 구조를 이용해 최댓값/최솟값을 반복적으로 꺼내며 정렬합니다.
• 핵심 복잡도는 O(N log N).

코드

void HeapSort(std::vector<int>& v) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    for (int num : v) pq.push(num);
    v.clear();
    while (!pq.empty()) {
        v.push_back(pq.top());
        pq.pop();
    }
}

• 위 방식은 priority_queue를 써서 구현 이해가 쉽습니다.
• 표준 힙 알고리즘(make_heap, sort_heap)을 쓰는 방식도 있습니다.

---

병합 정렬 (Merge Sort)

원리

• 분할 정복: 반으로 나누고, 정렬된 두 구간을 merge.
• 분할 깊이 O(log N), merge O(N) → O(N log N).

핵심

• "정렬된 두 구간을 합치는 것"이 쉽다는 아이디어.
• 크래프톤 면접에서 "정렬된 두 벡터 합치기" 형태로 출제된 사례.
• 안정 정렬(Stable)이라는 장점이 있지만, 보통 O(N) 추가 메모리가 필요합니다.

---

퀵 정렬 (Quick Sort)

원리

• 피벗을 기준으로 왼쪽(작은 값), 오른쪽(큰 값) 분할. 재귀적으로 정렬.
• 평균 O(N log N), 최악 O(N²).
• 이름처럼 평균적으로 가장 빠른 정렬로 알려짐.
• 피벗 선택(랜덤/중앙값 근사)에 따라 실제 성능이 크게 달라집니다.

Partition 핵심

• low: pivot보다 작거나 같을 때까지 오른쪽으로 이동.
• high: pivot보다 클 때까지 왼쪽으로 이동.
• low < high이면 swap. 최종적으로 pivot과 arr[high] swap.

---

실무 정렬 패턴

• 인벤토리 정렬: 희귀도, 부위, 착용 여부 등 기준.
• 서치 결과 정렬: 거리, 희귀도 등 우선순위.
• 버튼 클릭 시 한 번만 정렬 → N log N도 부담 없음.

추가로 자주 쓰는 도구:

std::partial_sort(v.begin(), v.begin() + k, v.end()); // 상위 k개만 정렬
std::nth_element(v.begin(), v.begin() + k, v.end());  // k번째 기준 분할

---

시간 복잡도 비교

알고리즘	평균	최악	안정성
버블 정렬	O(N²)	O(N²)	안정
선택 정렬	O(N²)	O(N²)	불안정
힙 정렬	O(N log N)	O(N log N)	불안정
병합 정렬	O(N log N)	O(N log N)	안정
퀵 정렬	O(N log N)	O(N²)	보통 불안정
std::sort	O(N log N)	O(N log N) (비교 횟수 기준)	불안정

• 일반적으로 성능 관점 순서는 O(N) < O(N log N) < O(N²)입니다.

---

자주 하는 실수 + 체크 질문

자주 하는 실수

실수	문제
comparator를 <=로 작성	strict ordering 위반으로 비정상 동작 가능
list에 std::sort 호출	컴파일 오류 (Random Access Iterator 필요)
동등 키 순서 보존이 필요한데 sort 사용	기존 순서가 섞일 수 있음 (stable_sort 필요)
정렬 후 재사용할 데이터에 불필요한 전체 sort 반복	partial_sort/nth_element가 더 적합할 수 있음

체크 질문 (스스로 답해보기)

• std::sort와 std::stable_sort의 차이를 설명할 수 있는가?
• comparator에서 왜 a <= b 대신 a < b 형태가 기본이 되는가?
• 상위 10개만 필요할 때 전체 정렬 대신 어떤 알고리즘을 고려할 수 있는가?

---