무작위화 등 적절하게 partition의 위치를 균등하게 만드는 기법이 없다면 quick sort의 시간 복잡도는 O(N^2)입니다.
최악의 경우에도 O(NlogN)에 정렬이 가능한 heap sort, merge sort 등으로 교체하시는 것을 추천합니다.
1620번 - 나는야 포켓몬 마스터 이다솜
무작위화 등 적절하게 partition의 위치를 균등하게 만드는 기법이 없다면 quick sort의 시간 복잡도는 O(N^2)입니다.
최악의 경우에도 O(NlogN)에 정렬이 가능한 heap sort, merge sort 등으로 교체하시는 것을 추천합니다.
댓글을 작성하려면 로그인해야 합니다.
shs9064 9달 전
기존에 버블정렬을 사용하여 제출 후 시간초과가 발생하여 이를 퀵정렬로 수정하여 재제출 하였음에도 여전히 시간초과가 뜨고 있습니다.
최대한 C언어로 베이직하게 해보고 싶어서 편의성을 위한 최소한의 라이브러리만 사용하고자 하였습니다.
전체 코드 플로우는
이름 오름차순 정렬 -> 이름 입력 시 검색 수행 -> 답 출력입니다
예외 처리 등 누락된 것이 있다면 피드백 주시면 감사드리겠습니다!!