앞에서 배웠던 알고리즘은 직관적이었지만 실행 시간의 상한이 다소 높았는데요 그 이유는 반복되는 작업이 많았기 때문입니다. 그래서 이번엔 저번 포스팅에서 공부했던 재귀를 활용하여 보다 더 효율적인 정렬 알고리즘을 만드는 법에 대해 공부해보도록 하겠습니다.
버블 정렬, 선택 정렬 같이 다양한 정렬 방법에 대해 배웠는데 아직 공부하지 않은 대표적인 정렬방법이 하나 더 있습니다. 바로 병합 정렬(합병 정렬이라고도 합니다.)입니다. 병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식입니다.
만약 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에서 한글 강의로도 들을 수 있습니다.
'CS 기초 > 알고리즘' 카테고리의 다른 글
[CS50] 재귀 (0) | 2021.08.16 |
---|---|
[CS50] 정렬 알고리즘의 실행시간 (0) | 2021.08.15 |
[CS50] 선택 정렬 (0) | 2021.08.14 |
[CS50] 버블 정렬 (0) | 2021.08.14 |
[CS50] 선형 검색 (0) | 2021.08.13 |