std::list가 sort를 멤버 함수로 제공하는 이유
C++·2025. 12. 3.
1. std::sortstd::sort와 반복자 요구사항std::sort는 C++ 표준에 따라 평균적으로 O(N log N)의 시간 복잡도를 보장해야 합니다. 이를 위해 대부분의 STL 구현체는 인트로소트(Introsort)라는 하이브리드 정렬 알고리즘을 사용합니다. 인트로소트는 퀵소트(Quicksort)를 기반으로 하되, 재귀 깊이가 깊어지면 힙소트(Heapsort)로 전환하고, 데이터 크기가 작아지면 삽입정렬(Insertion Sort)을 사용하는 방식으로 최악의 경우에도 O(N log N)을 보장합니다.이러한 알고리즘, 특히 퀵소트의 핵심은 임의 접근(Random Access)을 통해 효율적으로 동작한다는 점입니다. 퀵소트의 파티션(partition) 과정에서는 피벗(pivot)을 기준으로 컨테이너..
