[자료구조] 합병 정렬 (merge sort)CSE/자료구조 (data structure)2022. 11. 13. 00:00
Table of Contents
반응형
합병 정렬이란?
합병 정렬은 리스트를 분할하고 결합하는 과정 속에서 정렬을 수행하고자 하는 방법입니다. 분할-정복에 따른 수행 방식입니다.
앞서 정렬을 할 때는 기존의 리스트를 그대로 이용해서 수행했습니다. 숫자가 적을 때는 시간이 오래 걸리지 않지만, 커지면 시간 복잡도에 따라 수행 시간이 어마하게 늘어남을 알 수 있습니다.
합병 정렬은 기존의 리스트를 쪼개서 더 작은 리스트를 만듭니다(분할). 쪼갤 수 있을 때까지 쪼갭니다(정복) 문제를 충분히 작게 만들었다면, 정렬을 합니다. 이 때 정렬은 숫자 단 두개만을 비교합니다.
정렬을 했다면, 다시 원래 리스트의 크기로 돌아갈 있도록 합쳐줍니다(결합). 합쳐주는 과정에서도 순서대로 숫자가 들어가야 합니다. 따라서 분리되어 있는 리스트의 맨 앞에서 하나씩 꺼내 비교해주면서 넣어줍니다.
합병 정렬 구현
합병 정렬의 핵심은 분할-정복-결합
입니다.
과정은 아래와 같습니다.
- 하나의 리스트를 두 리스트로 분할
- 단, 각각의 리스트를 분할할 수 있다면 1.을 다시 수행
- 분할된 부분 리스트 정렬
- 정렬된 리스트 결합
- 단, 각각의 리스트를 결합할 수 있다면 3.을 다시 수행
코드로 구현하면 아래와 같습니다.
void merge(int list[], lit left, int mid, int right) {
int i = left, j = mid + 1, k = left, l;
while(i <= mid && j <= right) {
if(list[i] <= list[j]) {
sorted[k++] = list[i++];
} else {
sorted[k++] = list[j++];
}
}
if(i > mid) {
for(l = j; l <= right; l++) {
sorted[k++] = list[l];
}
} else {
for(l = i; l <= mid; l++) {
sorted[k++] = list[l];
}
}
for(l = left; l <= right; l++) {
list[l] = sorted[l];
}
}
void merge_sort(int list[], int left, int right) {
int mid;
if(left < right) {
mid = (left + right) / 2;
merge_sort(list, left, mid);
merge_sort(list, mid + 1, right);
merge(list, left, mid, right);
}
}
합병 정렬의 시간 복잡도
합병 정렬은 최악, 최선, 평균 모두 $O(n \space log \space n)$에 수행됩니다.
728x90
반응형
'CSE > 자료구조 (data structure)' 카테고리의 다른 글
[자료구조] 힙 정렬 (heap sort) (0) | 2022.11.15 |
---|---|
[자료구조] 퀵 정렬 (quick sort) (0) | 2022.11.14 |
[자료구조] 셸 정렬 (shell sort) (0) | 2022.11.12 |
[자료구조] 버블 정렬 (bubble sort) (0) | 2022.11.11 |
[자료구조] 삽입 정렬 (insertion sort) (0) | 2022.11.10 |
@junyeokk :: 나무보다 숲을
컴퓨터 전공 관련, 프론트엔드 개발 지식들을 공유합니다. React, Javascript를 다룰 줄 알며 요즘에는 Typescript에도 관심이 생겨 공부하고 있습니다. 서로 소통하면서 프로젝트 하는 것을 즐기며 많은 대외활동으로 개발 능력과 소프트 스킬을 다듬어나가고 있습니다.
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!