C 라이브러리의 qsort는 퀵소트로 구현해야 한다는 명세 자체가 없습니다. 이름만 퀵소트에서 따왔을 뿐 내부적으로는 퀵소트가 전혀 아닌 것을 사용하고 있을 수도 있고, 퀵소트라고 하더라도 단순히 정렬된 상태로만 입력이 주어져도 O(n^2)의 시간이 걸리는 기본형을 쓰지는 않을 것입니다. 직접 퀵소트를 구현하면 여러 최적화 기법을 쓰지 않는 한 단순한 데이터에 대해서도 O(n^2)이 될 수 있으므로 직접 정렬을 구현할 거라면 병합 정렬같이 O(nlogn)이 보장되는 것을 쓰시기를 권장합니다.
rimm39 2년 전
qsort로 배열을 정렬하고 이진 탐색으로 찾았습니다
stdlib의 qsort를 사용하면 답이 맞는걸로 봐서 qsort 구현이 잘못된 것 같은데
어떤 부분 때문에 시간이 초과되는지 궁금합니다