daisy7024   5년 전

Merge Sort로 구현해서 문제를 풀거나 C++의 algorithm에 있는 sort 함수를 이용하면 손쉽게 풀 수 있는데

궁금해서 native quick sort 소스코드를 이용해서 풀어봤는데 시간 초과가 뜨더라고요.

이게 최악의 테스트 케이스가 적용되어서 O(n^2)가 되어서 그런 건지 제가 구현을 잘못 한 것인지 모르겠어서 질문드립니다.

djm03178   5년 전

최악의 케이스라는 게 다름 아닌 이미 정렬된 상태로 입력이 들어오는 것이기 때문에 naive한 퀵소트면 어느 문제든 시간 초과가 날 가능성이 매우 높습니다.

daisy7024   5년 전

아 그렇군요! 감사합니다 문제를 풀 때 가급적이면 Native한 퀵소트는 사용하지 않는 편이 좋겠네요.

djm03178   5년 전

native가 아니라 naive입니다. '순진한' 이라는 뜻입니다.

daisy7024   5년 전

아하 덕분에 헷갈렸던 것도 바로잡고 가네요 감사합니다.

Green55   5년 전

직접 퀵소트를 구현해야하는 상황이라면 pivot을 잡을 때 랜덤하게 선택하시면 상당히 좋은 효과를 보실 수 있습니다.

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