dnjstjr0227   6년 전

qsort와 partition부분은 1번조건인 strlen길이로 소팅하는부분이고

qqsort와 ppartition부분은 2번조건인 strcmp로 같은길이일때만 사전순비교하면서 소팅하게했습니다..

그리고 마지막으로 겹치는부분일때는 시간조금이라도 줄여볼라고 따로 어레이에 변화는 안주고 프린팅만 안나오게 해놨습니다..

첨에 버블로 걍짰다가 시간초과떠서 퀵소트로 짜본건데

nlogn인데도 잘 안됐나보네요 ㅠㅠ

어떤게 문제인지 알고싶습니다..ㅠㅠ

정말로 5시간이상은 쓴거같네요..ㅠㅠㅠㅠ

kimsy96   6년 전

퀵정렬은 최악의 경우 복잡도가 O(n^2)이라서..

특히 저렇게 피봇값을 대충? 만들면 최악이 만들어질가능성도높구요..

c나 c++에서 제공하는 정렬함수를한번써보시는게 

dnjstjr0227   6년 전

답변감사합니다! 이거보고 

pivot값 정하는 함수로 left 중간 right

이렇게 세개중에 중간값으로 pivot결정하는 함수 추가했는데도 

시간초과가 뜨네요..ㅠㅠㅠㅠㅠㅠㅠㅠㅠ

머지소트로 다시 짜봐야될까봐요 ㅠㅠ

있는함수쓰는거보다 직접짜보고 싶어서용

많은도움이 됐습니다!

kimsy96   6년 전

머지소트ㄴ로 구현하면 아마될겁니다. 최악의경우에도 nlgn으로 알고있고있습니다..아마도

dnjstjr0227   6년 전

넵 한번짜보겠습니다!!

정말감사합니다 ㅎㅎ

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