C++의 <algorithm> 헤더에 있는 sort와 stable_sort를 공부를 하다가
sort의 내부적인 sort인 '퀵소트' vs stable_sort의 내부적인 sort인 '머지소트'
가 궁금해져서 이렇게 알고리즘에 대해 살짝 공부를 해보기로 했습니다.
[Algorithm] Quick Sort, Merge Sort 비교체험 !
이전글에 계속하여.. Quick Sort vs Merge Sort 알고리즘 수업시간에 귀가 따갑도록 들었던 이 두 정렬방법. 당연히 퀵이 빠른거 아니야? 했지만, 누군가는 데이터가 커질수록 Merge가 좋다하고.. 음음 직
penpen.tistory.com
이 블로그에 굉장히 잘 나와있다.
결론적으로는 배열을 10,000부터 천만까지 늘려나갔을 때의 결과는
모든 경우에서 퀵소트의 우승!!
그렇다면 왜 둘의 시간 복잡도는 모두 O(nlogn)인데 차이가 생길까?
머지소트가 시간이 더 많이 걸리는 이유는 "배열을 생성하는 시간"이 존재하기 때문이다.
그렇다면 당연하게도 배열을 크게 생성하면 할 수록 머지소트가 더 많이 걸린다.
어마어마하게 치이는 나지 않아서 sort와 stable_sort의 특징을 알아보고
자신에게 필요한 sort를 사용한다면 좋을 것 같다.
'알고리즘 공부' 카테고리의 다른 글
| A* 알고리즘 (0) | 2024.03.10 |
|---|---|
| merge sort - 병합 정렬 정리 (1) | 2021.02.07 |
