이건 qsort 가 잘못 구현된 것 같습니다.
이 qsort 는 배열의 모든 원소가 같을 때 (ex. {5, 5, 5, 5, 5, 5 ....}) O(n2) 에 작동합니다.
아래 코드를 돌려 보면 start 값이 1씩만 늘어남을 확인할 수 있습니다.
이는 모든 원소가 같으면, right 가 배열의 거의 처음 부분까지 가 버려서 그런 것으로 보입니다.
아래의
qsort(target, start, right - 1);
qsort(target, right + 1, end);
이것을,
qsort(target, start, right - 1);
qsort(target, left, end);
이런 식으로 고치면 아마 될 것 같네요.
limd123 2년 전
정렬하는데 걸리는 시간 nlog n 이고 답 찾는데 n걸려서 결론적으로 시간복잡도가 nlogn인데 왜 시간초과가 나는지 모르겠습니다.