정렬 (Sort)

---

전날 내용 요약 — 해시 (Hash)

• 해시는 key를 해시 함수로 변환해 배열 인덱스에 직접 접근 → 평균 O(1) 탐색
• unordered_map: 해시 기반, O(1) / map: 레드-블랙 트리, O(log N)
• 해시 충돌 해결: 체이닝(unordered_map 방식), 개방 주소법
• []는 없는 키를 자동 삽입 → 읽기만 할 땐 find() 또는 count() 사용

---

정렬이란?

정해진 규칙에 따라 정리를 하는 것.
다른 알고리즘을 사용하기 위한 전처리 단계로 많이 쓰임.(그 자체를 목적으로서 쓰이는 경우도 있음)

---

기본 sort()

#include <algorithm>
#include <vector>
using namespace std;

vector<int> v = {5, 3, 1, 4, 2};

sort(v.begin(), v.end());                     // 오름차순: 1 2 3 4 5
sort(v.begin(), v.end(), greater<int>());     // 내림차순: 5 4 3 2 1

---

커스텀 비교 함수

sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);  //절댓값 기준 오름차순
});

---

다중 정렬 기준

vector<pair<int,int>> v = { {3,2},{1,5},{3,1},{1,2} };

sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
    if (a.first != b.first) return a.first < b.first;  // 기준 1: first 오름차순
    return a.second > b.second;                         // 기준 2: second 내림차순
});
// 결과: (1,5) (1,2) (3,2) (3,1)

---

sort vs stable_sort

	sort	stable_sort
시간복잡도	O(N log N)	O(N log² N)
동일 원소 순서	보장 안 함	보장 함

원래의 순서가 의미가 있는 경우에 stable_sort를 주로 사용함.

---

Strict Weak Ordering

비교 함수가 잘못 작성되는 경우에 런타임 에러 혹은 무한 루프가 발생함.

// ❌ 잘못된 예: a == b일 때 true 반환
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;
});

// ✅ 올바른 예
sort(v.begin(), v.end(), [](int a, int b) {
    return a < b;
});

같은 원소끼리의 비교 시, 반드시 ‘false’를 반환해야 함.

---

시간복잡도

알고리즘	평균	최악	비고
std::sort	O(N log N)	O(N log N)	인트로소트
std::stable_sort	O(N log² N)	O(N log² N)	순서 보장
버블/선택/삽입 정렬	O(N²)	O(N²)	n이 10000 이상인 경우 1초 안에 통과가 어려움

• algorithm
• sort
• c