728x90
반응형
알고리즘 - 합병 정렬 (Merge Sort)
하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
합병 정렬은 분할 - (정복) - 결합의 단계로 이루어진다.
- 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
- 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.
- 결합 : 정렬된 부분 배열들을 하나의 배열에 합병한다.
합병 정렬은 추가적인 리스트가 필요하며 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다. 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병하는 단계이다.
[ 시간복잡도 ]
크기가 N인 배열을 반으로 쪼개면서 분할해 나가기 때문에 시간복잡도는 O(NlogN)이다.
- 크기가 N인 배열을 둘로 쪼개서 다시 정렬된 배열로 병합할 때는 비교의 횟수가 N번을 넘지 않는다. 길이가 N/2인 배열을 정렬하는데에는, N/4의 길이를 가지는 배열 두 개를 정렬하므로, 이것의 비교연산 횟수는 N/2이다. 전체로 보면, 길이가 N/4인 배열을 두개씩 합병하여 정렬된 N/2배열을 두 개 만드는 작업을 수행하는데 드는 비교연산의 횟수는 2*N/2 = N이다. 모든 경우 비교연산 횟수는 N이다. 길이가 N인 배열을 길이가 1인 각각의 리스트로 쪼개려면, 아래의 표에서 봤을 때 트리의 레벨은 logN이 된다. 따라서 총 횟수는 N*logN이다.
[ 예시 ]
상세 과정
728x90
반응형
'BASE > Alogorithm' 카테고리의 다른 글
| 알고리즘 - 너비 우선 탐색 (Breadth First Search) (0) | 2021.01.27 |
|---|---|
| 알고리즘 - 깊이 우선 탐색 (DFS, Depth-First Search) (0) | 2021.01.27 |
| 알고리즘 - 이진 탐색 (Binary Search) (0) | 2021.01.26 |
| 알고리즘 - 선택 정렬 (Selection Sort) (0) | 2021.01.11 |
| 알고리즘 - 삽입 정렬 (Insertion Sort) (0) | 2021.01.11 |
댓글