병합정렬,퀵정렬 속도 질문
조회수 792회
알고리즘 공부중에 퀵정렬과 병합정렬 을 c로 구현하여 clock 함수를 이용해 속도비교를 해봤는데 보통의 경우 퀵정렬이 병합정렬보다 좋은 성능을 낸다고 알고 있었는데 소스를 컴파일해서 시간을 비교해보니 병합정렬이 더 빠르게 나오더라고요.
배열의 크기를 10000 이하로 정하고 완전히 랜덤한 수(0~10000)를 정렬하는 경우에 병합정렬이 퀵정렬보다 빠르게 나오는것이 정상인가요? 아니면 제가 퀵정렬 구현을 잘 못해서 그런걸까요?
퀵정렬이 더 빠르다는것은 pivot을 잘 정하는 알고리즘으로 짰을떄 인가했는데(저는 pivot을 배열의 맨왼쪽으로 고정했습니다.)완전히 랜덤한 수들을 정렬하는거라서 상관없을것같고.. 열심히 고민은 해보는데 답이 잘 안나오네요 ㅜㅜ
처음 질문올려보는거라 잘못된점이 있다면 말해주세요 고치겠습니다. :)
-
(•́ ✖ •̀)
알 수 없는 사용자
1 답변
-
찾아보니 그렇게 놀랄 일은 아닌 듯합니다.
Efficiency :
Merge sort is more efficient and works faster than quick sort in case of larger array size or datasets.
whereas
Quick sort is more efficient and works faster than merge sort in case of smaller array size or datasets.요컨대 대상 배열이 크면 병합정렬 쪽이 더 낫다는 말인데, 사실 원소가 1만개 있는 배열은 큰 배열 축에 들거든요. 그러니 경험하신 현상은 코딩이 잘못됐다기보다는 얼추 예상 가능한 경우 같습니다.
댓글 입력