mkleeboy3   2년 전

Mergesort로는 됐는데

Random Pivot으로 골라서 Quicksort를 구현했는데 시간초과가 뜨네요.

간편함을 위해서 인덱스만 정렬했습니다. 

퀵소트로는 정녕 해결이 안되는건가요?

퀵소트도 구현방법에 따라서 조금씩 차이가 나던데 혹시 두 인덱스 i, j를 양끝에서부터 시작해서 중간값을 pivot으로 정해서 구현한 퀵소트로는 해결이 될까요? 성능차이가 있을까요?

djm03178   2년 전

피벗을 랜덤으로 잡아도, 여전히 O(N^2)입니다. 모든 원소가 다 같을 때에 문제가 됩니다.

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