합병정렬(Merge Sort)

2016. 11. 9. 23:49Basic/Data Structure

반응형

합병정렬(Merge Sort)

합병정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것입니다.

이처럼 합병정렬은 분할-정복(Divide and Conquer) 기법에 바탕을 두고 있습니다.

- 얼핏보면 쉘 정렬과 비슷해보이지만 또 그렇지만은 않습니다.


1. 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할합니다.

2. 정복 : 부분 배열을 정렬합니다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 기법을 적용합니다.

3. 결합 : 정렬된 부분 배열들을 하나의 배열에 통합합니다.





합병정렬의 특징

삽입, 선택, 버블, 쉘 정렬 등의 이제까지 설명했던 정렬들 중 실행속도가 가장 빠릅니다. O(n log 2n)

합병정렬은 최적, 최악, 평균 속도를 가리지 않고 항상 일정한 속도를 냅니다.

단점으로는 임시 배열이 필요하다는 것

레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 시간적 낭비를 초래할 수 있습니다.

- 이 경우 레코드를 연결리스트로 구성하면 링크 인덱스만 변경되기 때문에 무시해도 됩니다.

연결리스트를 사용한다면 퀵 정렬을 포함해 가장 효율적인 정렬방법이 될 수 있습니다. (퀵 정렬은 다음에 포스팅 하겠습니다.)



합병정렬의 구현




출처 : http://wonjayk.tistory.com/221

반응형

'Basic > Data Structure' 카테고리의 다른 글

힙 정렬 (Heap Sort)  (0) 2016.11.09
퀵 정렬 (Quick Sort)  (0) 2016.11.09
쉘 정렬(Shell Sort)  (0) 2016.11.09
버블정렬 (Bubble Sort)  (1) 2016.11.09
삽입정렬 (Insertion Sort)  (0) 2016.11.09