2017. 4. 29. 22:07
병합정렬(Merge Sort) 알고리즘-자료구조2017. 4. 29. 22:07
정렬 중 O(nlogn)의 시간복잡도를 가진 방법으로, 개인적으로는 퀵소트나 힙정렬 보다는 구현이 간단하다.
정렬해야하는 원소가 적다면(정확한 것은 모르겠지만 5개 이하) 삽입정렬이 더 낫다고도 한다.
스택오버플로우를 보면 퀵 정렬이 최악의 경우 O(n^2)임에도 여러가지 이유로
병합 정렬보다 나은 성능을 보인다고 하는데, 확인해보아야 할 듯 싶다.
C++ std library에는 퀵 정렬과 힙 정렬을 적당히(?) 활용한 Intro sort라는 게 쓰이는 듯 하다.
(http://stackoverflow.com/questions/70402/why-is-quicksort-better-than-mergesort)
https://gist.github.com/woo972/0924604b96188cb78b9cf8b1a34fbd19
'알고리즘-자료구조' 카테고리의 다른 글
| SegmentTree(구간트리) (0) | 2017.02.19 |
|---|
