CS50 2019 강의를 듣고 내용을 정리한 시리즈 글입니다.
학습목표
재귀를 활용한 병합 정렬을 구현할 수 있습니다.
핵심 단어
- 병합 정렬
강의 내용
1. 병합 정렬
병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다.
다음 숫자들을 오름차순으로 정렬해보자.
7 4 5 2 6 3 8 1
# 숫자들을 반으로 나눈다.
7 4 5 2 | 6 3 8 1
# 첫번째 부분을 다시 반으로 나눈다.
7 4 | 5 2 | 6 3 8 1
# 반복하여 다시 반으로 나눈다.
7 | 4 | 5 2 | 6 3 8 1
# 더 이상 나눌 수 없기 때문에 이제 병합한다.
# 이 때, 작은 숫자가 먼저 오도록 병합한다.
4 7 | 5 2 | 6 3 8 1
# 4 7 과 5 2 를 병합한다.
# 여기서도 각 부분들의 숫자들을 비교하여 더 작은 숫자가 먼저 오도록 병합한다.
2 4 5 7 | 6 3 8 1
# 오른쪽 부분도 동일한 과정을 통해 나누고 병합한다.
2 4 5 7 | 1 3 6 8
# 마지막으로 동일한 방법으로 두 부분을 병합한다.
1 2 3 4 5 6 7 8위와 같은 방법을 병합정렬이라고 한다.
병합 정렬 실행 시간의 상한은 숫자들을 반으로 나누는 데 O(log n), 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문에 O(n log n)이 된다.
실행 시간의 하한도 정렬 여부에 관계 없이 나누고 병합하는 과정이 필요하기 때문에 Ω(n log n)이 된다.
생각해보기
병합 정렬을 선택 정렬이나 버블 정렬과 비교했을 때 장점과 단점은 무엇이 있을까요?
병합 정렬은 처리속도가 빠르지만 메모리가 많이 필요할 수 있다.
병합 정렬은 정렬 여부에 관계 없이 항상 진행이 되기 때문에 최적화가 불가능하다.
(버블 정렬에서는 더 이상 교환할 수 없을 때 멈추는 최적화 기법을 사용할 수 있다.)
