angela0102   6년 전

퀵정렬로 문제를 풀었는데, 시간초과라고 나옵니다...ㅠㅠ

jh05013   6년 전

퀵정렬은 최악의 경우 O(n^2)이 걸립니다.

djm03178   6년 전

naive한 퀵소트는 항상 최악의 경우 O(N^2)이 걸린다는 것을 고려해야 하고, 특히 온라인 저지의 입력 데이터에는 이런 케이스가 들어있을 가능성이 아주 높습니다. 그냥 이미 정렬이나 역정렬된 상태의 입력을 주면 되기 때문이죠. 정렬 기능을 직접 구현하는 게 목표라면 병합 정렬이나 힙 정렬, 아니면 좀 더 보완된 퀵 정렬 등을 구현하셔야 합니다. 아니면, 그냥 stdlib.h에 있는 qsort 쓰세요.

댓글을 작성하려면 로그인해야 합니다.