'내장되어있는 퀵소트'가 정확히 뭘 말씀하시는 건지 모르겠습니다.
C의 내장 정렬 함수 qsort는 퀵소트에서 이름을 따오기는 했지만 실제로 무엇으로 구현하라는 것은 표준에 정의되어있지 않습니다. 라이브러리가 정하기 나름이기 때문에, 퀵소트를 쓸 수도 있고, 변형된 퀵소트를 쓸 수도 있고, 무조건 nlogn이 보장되는 다른 정렬을 쓸 수도 있습니다.
C++의 내장 정렬 함수 std::sort는 최악의 경우 nlogn을 보장하게끔 표준에 명시되어있기 때문에 일반적인 퀵소트를 사용하지 않습니다. 이것 역시 정확히 뭘 사용하라고 적혀있지는 않지만, gcc의 경우는 introsort라는 퀵소트 + 힙소트 + 삽입 정렬의 하이브리드 정렬법을 사용해서 복잡도를 보장합니다.
joseph415 4년 전
데이터가 정렬되어있을 경우 퀵 소트의 최악의 시간복잡도가 n^2이잖아요
근데 보통 내장된 sort함수가 퀵소트로 되어있을텐데 이 퀵 소트들은 n^2 시간복잡도가 안나오게
피봇을 랜덤으로 설정하던가 등등 여러 방법들을 써서 n^2을 피하게 만들어져있나요???
알고리즘 풀다가 갑자기 궁금해져서 질문올립니다!