알고리즘

정렬 (Sorting)

데이터를 특정 기준으로 순서를 매기는 알고리즘군. 비교 기반 정렬은 O(n log n) 이 하한이다.

핵심 포인트

• 퀵 정렬: 평균 O(n log n), 최악 O(n²) — 피벗 선택이 핵심
• 병합 정렬: 항상 O(n log n), 안정 정렬, O(n) 추가 공간 필요
• 힙 정렬: O(n log n), 제자리 정렬, 불안정 정렬
• 계수 정렬: O(n + k), 값 범위가 작을 때 선형 정렬 가능