Search
Duplicate
📗

Intro sort

간단소개
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
C++
Scrap
태그
STL
9 more properties

Summary

STL의 정렬 알고리즘(std::sort)은 정확히 말하면 퀵 소트가 아니고, 엄밀히 말하면 intro sort라는 알고리즘을 쓴다고 말할 수 있습니다.
Quick sort 같은 경우 최악의 경우 O(n^2)의 시간복잡도를 보이기 때문에, 최악의 경우에도 O(nlogn)을 유지해주기 위한 변형이 가해진 알고리즘입니다.
비교 기반의 정렬 알고리즘은 이보다 더 빠를 수 없고, stl sort구현이 속도가 느린 구현이 아니기 때문에 일반적으로 정렬이 필요한 상황에서는 그냥 사용하면 된다고 합니다.
원본