jow1025   4년 전

시간상 무난하게 mergesort이용해야하는건알겠는데 초보라 구현을 어려워하다보니...이해가안가서

찾아보다가 퀵정렬함수를 이용한 풀이를보았습니다. 그런데 제가 알기론 퀵정렬의경우 최악의경우

o(n^2)으로써 예제의경우 4억으로써 약4초가떠서 오답이나야하지않나요?

그리고 아래의 코드의 몇군데를 주석친 코드로 바꿔서 제출하면 중복된 값이 연속해서 나오고 그외에는 똑같이나오는데요 

이유를 알수잇을까요?

숫자만정렬하다가 문자열정렬하려니 어렵네요..

djm03178   4년 전

qsort는 quick sort에서 이름을 따오기는 했지만 내부가 우리가 익히 아는 순수한 퀵소트로 된 건 아닙니다. 애초에 어떤 정렬로 구현해야 한다는 것 자체가 표준에 정의되어있지 않고, gcc에서는 보통의 퀵소트보다는 더 안정성 있는 구현체를 사용해서 보통의 데이터로는 잘 저격이 안 되는 것으로 알고 있습니다.

jow1025   4년 전

답변감사합니다. 그러면 알고리즘대회나 코딩테스트에서는 위와같은 방법보다는 mergesort나o(n^2)이 나오지않는 정렬방법을 써야되는건가요?

djm03178   4년 전

웬만하면 qsort가 저격당할 일은 없으니 그냥 쓰셔도 됩니다.

그보다는 C++을 배우셔서 nlogn이 무조건 보장되는 std::sort를 쓰시는 편이 편할 것 같습니다.

jow1025   4년 전

감사합니다 !

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