shfshfdl   6년 전

library를 쓰면 안되는 상황이라 qsort를 구현해서 입맛에 맞게 사용하고 싶은데

답은 도출되었지만 시간초과가 납니다.

아무래도 qsort의 조건이나 cmp 부분이 잘못된거 같은데..

아무리 봐도 이해가 되지 않아서 문의드립니다....

도움 부탁드리겠습니다.

chogahui05   6년 전

답은 도출되었다. 알고리즘은 맞으시다는 거네요.

그렇지만 시간 초과가 났다.


오름차순, 혹은 내림차순으로 정렬이 되어 있을 때 시간초과가 날 거 같네요..

피벗 선택하는 방법 중에 중위법이라고 하는 게 있습니다.


간단하게 말하면

가장 좌측에 있는 것. 우측에 있는 것, 중간에 있는 것을 고른 다음에..

이 셋을 비교해서 중간값을 가지는 것을 피벗값으로 택한다. 이런 건데요..

한 번 검색해 보시는 것도 괜찮으실 거 같네요.

shfshfdl   6년 전

답변 감사합니다

우선 검색해서 적용 충분히 해보고 추가 질문있으면 또 드리겠습니다.

감사합니다!

shfshfdl   6년 전

중위법을 적용하여 문제를 풀어봣는데....
정렬이 정상적으로 되지 않아요 ...ㅠㅠ
비교 부분이 문제인거같은데 어떻게 고쳐야 맞는답이 도출되는지 모르겠습니다.


도움 부탁드리겠습니다...

irishw   6년 전

quick sort는 O(N)을 보장하지않습니다

삼성 SW자격검증 준비하시나요?

정렬이 문제고 라이브러리 쓰지못

하는 상황이라면 

merge sort해보세요..

chogahui05   6년 전

??

알고리즘이 3값의 중위값을 피벗으로 택하는.

예를 들어서

가장 왼쪽에 있는 값이 0, 중앙에 있는 값이 9, 우측에 있는 값이 3이라면

중위값은 3이 나와야 합니다.


이쪽 한 번 참고해 보세요.

https://stackoverflow.com/ques...

irishw   6년 전

앗.... 답을 잘못 달았었네요..


quick sort 는 최악의 경우에 O(N)이 아니라 O(logN)을 보장 하지 않습니다.


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