[CS50] 병합 정렬

앞에서 배웠던 알고리즘은 직관적이었지만 실행 시간의 상한이 다소 높았는데요 그 이유는 반복되는 작업이 많았기 때문입니다. 그래서 이번엔 저번 포스팅에서 공부했던 재귀를 활용하여 보다 더 효율적인 정렬 알고리즘을 만드는 법에 대해 공부해보도록 하겠습니다.

 

버블 정렬, 선택 정렬 같이 다양한 정렬 방법에 대해 배웠는데 아직 공부하지 않은 대표적인 정렬방법이 하나 더 있습니다. 바로 병합 정렬(합병 정렬이라고도 합니다.)입니다. 병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식입니다.

만약 4 3 8 2 6 7 1 5 숫자 리스트를 병합 정렬을 사용해 오름차순으로 정렬해본다면

1.   4 3 8 2 | 6 7 1 5      // 숫자들을 반으로 나눈다.

2.   4 3 | 8 2 | 6 7 1 5    // 나눠진 부분을 한번 더 나눈다.

3.   4 | 3 | 8 2 | 6 7 1 5  // 나눠진 부분을 한번 더 나눈다. (여기서 나눈 부분의 원소가 한개가 됩니다.)

4.   3 4 | 8 2 | 6 7 1 5   // 더이상 나눌 수 없으므로 두 숫자를 다시 병합한다. (이때 작은 숫자가 앞으로 오도록 한다.)

5.   3 4 | 8 | 2 | 6 7 1 5 

6.   3 4 | 2 8 | 6 7 1 5  // 마찬가지로 8 2 부분도 한개로 나눠서 새로 병합한다.

7.   2 3 4 8 | 6 7 1 5   // 이제 3 4와 2 8 부분을 작은 숫자가 앞으로 오게 병합한다.

....

n.   1 2 3 4 5 6 7 8     // 오른쪽 부분도 위와 동일한 과정을 거쳐 병합한다.

 

병합 정렬 실행 시간의 상한은 O(n log n)입니다.

이는 숫자를 반으로 나누는데 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬 후 병합하는데 각각 O(n)의 시간이 걸리기 때문입니다.

하한 역시 마찬가지로 Ω(n log n)으로 표시할 수 있습니다. 하한에서는 정렬의 여부와 관계없이 어차피 숫자를 다 나눠서 새로 병합하는 과정이 필요하기 때문입니다.

 

선택 정렬(Selection sort), 버블 정렬(Bubble sort), 병합 정렬(Merge sort)의 처리 속도를 살펴보면

 

병합 정렬 < 선택 정렬 < 버블 정렬이 됩니다.

---

출처

본 내용은 CS50의 2019년 강의를 듣고 작성했습니다. (개념이 어느 정도 정리되면 최신강의도 다시 듣고 수정할 내용 있으면 수정하겠습니다.)

 

강의 자료는 EdX에서 무료로 사용할 수 있고 boostcourse에서 한글 강의로도 들을 수 있습니다.