1920번 - 수 찾기
제가 배우기로는 merge sort 가 nlogn 을 보장해주며
quick sort 는 평균적으로는 nlogn, 최악에는 n^2 이라고 했는데
merge sort 사용 하면 1444 MS 가 걸리고
quick sort 를 사용하면 72MS 가 걸리네요?!!
quick sort 이정도로 merge 대비 더 빠른 알고리즘인가요?
소스는 머지와 퀵 소팅 코드 입니다.
자답합니다.
merge sort 안에 아래와 같이 메모리 잡는 부분이 문제였네요.
int buf[ITEMSIZE] = { 0 };
해당 변수를 매번 생성하지 않도록 수정하니 76MS 에 떨어졌습니다.
int buf[ITEMSIZE];
으로 초기화를 제외하고도 속도 차이가 동일한가요?
스택 메모리 영역에 primitive type의 배열을 할당하는 것이 저정도로 속도차이가 나는 것이 궁금해서 글 남겨봅니다.
와우! pl0892029님 말씀 처럼 초기화를 제거하니
buf 를 전역 변수로 뺀것과 동일한 속도가 나옵니다. 76MS
감사합니다.
댓글을 작성하려면 로그인해야 합니다.
righttime 6년 전
제가 배우기로는 merge sort 가 nlogn 을 보장해주며
quick sort 는 평균적으로는 nlogn, 최악에는 n^2 이라고 했는데
merge sort 사용 하면 1444 MS 가 걸리고
quick sort 를 사용하면 72MS 가 걸리네요?!!
quick sort 이정도로 merge 대비 더 빠른 알고리즘인가요?
소스는 머지와 퀵 소팅 코드 입니다.