righttime   2년 전

제가 배우기로는 merge sort 가 nlogn 을 보장해주며 

quick sort 는 평균적으로는 nlogn, 최악에는 n^2 이라고 했는데


merge sort 사용 하면 1444 MS 가 걸리고

quick sort 를 사용하면 72MS 가 걸리네요?!!


quick sort 이정도로 merge 대비 더 빠른 알고리즘인가요?


소스는 머지와 퀵 소팅 코드 입니다.

righttime   2년 전

자답합니다.


merge sort 안에 아래와 같이 메모리 잡는 부분이 문제였네요.

int buf[ITEMSIZE] = { 0 }; 


해당 변수를 매번 생성하지 않도록 수정하니 76MS 에 떨어졌습니다.

pl0892029   2년 전

int buf[ITEMSIZE];

으로 초기화를 제외하고도 속도 차이가 동일한가요?

스택 메모리 영역에 primitive type의 배열을 할당하는 것이 저정도로 속도차이가 나는 것이 궁금해서 글 남겨봅니다.

righttime   2년 전

와우! pl0892029님 말씀 처럼 초기화를 제거하니 

buf 를 전역 변수로 뺀것과 동일한 속도가 나옵니다.  76MS

감사합니다. 

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