1181번 - 단어 정렬
시간상 무난하게 mergesort이용해야하는건알겠는데 초보라 구현을 어려워하다보니...이해가안가서
찾아보다가 퀵정렬함수를 이용한 풀이를보았습니다. 그런데 제가 알기론 퀵정렬의경우 최악의경우
o(n^2)으로써 예제의경우 4억으로써 약4초가떠서 오답이나야하지않나요?
그리고 아래의 코드의 몇군데를 주석친 코드로 바꿔서 제출하면 중복된 값이 연속해서 나오고 그외에는 똑같이나오는데요
이유를 알수잇을까요?
숫자만정렬하다가 문자열정렬하려니 어렵네요..
qsort는 quick sort에서 이름을 따오기는 했지만 내부가 우리가 익히 아는 순수한 퀵소트로 된 건 아닙니다. 애초에 어떤 정렬로 구현해야 한다는 것 자체가 표준에 정의되어있지 않고, gcc에서는 보통의 퀵소트보다는 더 안정성 있는 구현체를 사용해서 보통의 데이터로는 잘 저격이 안 되는 것으로 알고 있습니다.
답변감사합니다. 그러면 알고리즘대회나 코딩테스트에서는 위와같은 방법보다는 mergesort나o(n^2)이 나오지않는 정렬방법을 써야되는건가요?
웬만하면 qsort가 저격당할 일은 없으니 그냥 쓰셔도 됩니다.
그보다는 C++을 배우셔서 nlogn이 무조건 보장되는 std::sort를 쓰시는 편이 편할 것 같습니다.
감사합니다 !
댓글을 작성하려면 로그인해야 합니다.
jow1025 4년 전
시간상 무난하게 mergesort이용해야하는건알겠는데 초보라 구현을 어려워하다보니...이해가안가서
찾아보다가 퀵정렬함수를 이용한 풀이를보았습니다. 그런데 제가 알기론 퀵정렬의경우 최악의경우
o(n^2)으로써 예제의경우 4억으로써 약4초가떠서 오답이나야하지않나요?
그리고 아래의 코드의 몇군데를 주석친 코드로 바꿔서 제출하면 중복된 값이 연속해서 나오고 그외에는 똑같이나오는데요
이유를 알수잇을까요?
숫자만정렬하다가 문자열정렬하려니 어렵네요..