[CS50] 알고리즘: 병합 정렬 (with. 알고리즘 실행시간 🌟)
❄️ David Malan 교수의 모두를 위한 컴퓨터 과학(CS50 2019)을 바탕으로 정리한 내용입니다.
병합 정렬
지난 단원에서 다양한 정렬 방법에 대해서 배웠습니다.
하지만 우리가 아직 공부하지 않은 대표적인 정렬 방법이 하나 더 있습니다.
전화번호부의 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 것과 공통점이 있는 방법인 병합 정렬(합병 정렬)이 있습니다.
병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식입니다.
그리고 이 과정은 재귀적으로 구현되기 때문에 나중에 재귀를 학습하면 더 이해하기 쉽습니다.
예시 1
마찬가지로 다음 숫자들을 오름차순으로 정렬해 보겠습니다.
먼저 숫자들을 반으로 나눕니다.
그리고 나눠진 부분 중 첫번째를 한번 더 반으로 나눠봅니다.
마지막으로 한 번 더 나눠봅니다.
이제 숫자가 두 개 밖에 남지 않았으므로 더 이상 나누지 않고, 두 숫자를 다시 병합합니다.
🌟 단, 이 때 작은 숫자가 먼저 오도록 합니다. 4와 7의 순서를 바꿔서 병합하는 것이죠.
마찬가지로 5 2 부분도 반으로 나눈 후에 작은 숫자가 먼저 오도록 다시 병합할 수 있습니다.
그럼 이제 4 7과 2 5 두 개의 부분들을 병합하겠습니다.
각 부분들의 숫자들을 앞에서 부터 순서대로 읽어들여 비교하여 더 작은 숫자를 병합되는 부분에 가져옵니다.
즉, 4와 2를 먼저 비교해서 2를 가져옵니다. 그 후에 4와 5를 비교해서 4를 가져옵니다.
그리고 7과 5를 비교해서 5를 가져오고, 남은 7을 가져옵니다.
이제 남은 오른쪽 4개의 숫자들도 위와 동일한 과정을 거칩니다.
마지막으로 각각 정렬된 왼쪽 4개와 오른쪽 4개의 두 부분을 병합합니다.
2와 1을 비교하고, 1을 가져옵니다. 2와 3을 비교하고, 2를 가져옵니다. 4와 3을 비교하고, 3을 가져옵니다.
4와 6을 비교하고… 이 과정을 병합이 끝날때까지 진행하면 아래와 같이 정렬이 완료됩니다.
전체 과정을 요약해서 도식화해보면 아래와 같습니다.
예시 2
이러한 방법을 ‘병합 정렬’ 이라고 합니다.
병합 정렬 실행 시간의 상한은 O(n log n) 입니다.
숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문입니다.
실행 시간의 하한도 역시 Ω(n log n) 입니다.
숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병합하는 과정이 필요하기 때문입니다.
(버블 정렬처럼 더이상 교환이 일어나지 않을 때 멈추는 최적화 기법은 없습니다. 힝상 왼쪽 절반을 정렬하고 오른쪽 절반을 정렬한 뒤 마지막으로 병합합니다.)
무언가를 계속해서 절반으로 나눈다면 -> 로그 함수로 표현할 수 있습니다.
💥 병합 정렬의 실행 시간? O(n log n)
n개의 숫자를 다시 합쳐야 하는데 log(n) 번 반복하기 때문입니다.
💛 개인 공부 기록용 블로그입니다. 👻