4: 알고리즘-8(병합 정렬:Merge sort)

병합 정렬(Merge sort): 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐 나가며 정렬을 하는 방식

전화번호부의 분할 정복 탐색처럼 데이터를 반으로 나누어 간다는 것과 공통점이 있음

버블 정렬이나 선택 정렬보다도 빠는 알고리즘

병합 정렬의 세 단계: 왼쪽 정렬, 오른쪽 정렬, 이 두 배열의 병합

 

병합정렬의 의사코드

 

If only one item       Return   Else       Sort left half of items       Sort right half of items       Merge sorted halves

---

임의의 숫자들을 오름차순으로 병합 정렬을 사용해 정렬하기

 

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

5) 이 때 숫자가 두 개 밖에 남지 않았으므로 더 이상 나누지 않고, 두 숫자를 다시 병합하고 작은 숫자가 먼저 오도록 함!     4 7 | 5 2 | 6 3 8 1

6) 같은 방법으로 5 2 부분도 반으로 나누고 작은 숫자가 먼저 오도록 병합     4 7 | 2 5 | 6 3 8 1

7) 4 7 과 2 5 부분을 병합하면서 숫자들을 앞에서부터 순서대로 읽고 비교해서 더 작은 숫자를 병합되는 부분에 가져옴     2 4 5 7 | 6 3 8 1

8) 나머지 오른쪽 4개의 숫자들도 동일한 과정을 거치기     6 3 8 1 → 3 6 1 8 → 1 3 6 8

9) 마지막으로 각각 정렬된 왼쪽 4개와 오른쪽 4개 두 부분을 병합함  2 4 5 7 | 1 3 6 8     2와 1비교, 1가져오고 / 2와 3비교, 2를 가져오고, .. 이 과정을 병합이 끝날 때까지 하면 정렬 완성

10) 1 2 3 4 5 6 7 8

전체 과정 도식화 7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분(숫자 1개)으로 나눠진 결과 4 7 | 2 5 | 3 6 | 1 8 → 숫자 1개씩을 정렬하여 병합한 결과 2 4 5 7 | 1 3 6 8 → 숫자 2개씩을 정렬하여 병합한 결과 1 2 3 4 5 6 7 8 → 숫자 4개씩을 정렬하여 병합한 결과

 

- 어떤 알고리즘을 말할 때 무언가를 절반으로 계속 나눈다면 로그 함수로 표현할 수 있음 

- 병합 정렬 실행 시간의 상한은 O(n log n) 

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

- 병합 정렬 실행 시간의 하한도 Ω(n log n)

→ 숫자들이 이미 정렬되었는지 여부에 상관없이 나누고 병합하는 과정이 필요하기 때문

- 장점: 최악의 경우 빠른 속도 단점: 최선의 경우(정렬된 경우) 같은 알고리즘 반복하기 때문에 시간 낭비, 많은 저장 공간 필요

---

실행시간을 나타내기 위해 사용되는 Big O 표기

 

O(n^2): 버블정렬, 선택정렬

O(n log n): 병합정렬

O(n): 선형검색

O(log n): 이진검색

O(1)

---

실행시간을 나타내기 위해 사용되는 Big Ω 표기

 

Ω(n^2): 선택정렬

Ω(n log n): 병합정렬

Ω(n): 버블정렬

Ω(log n)

Ω(1):선형검색, 이진검색

---

어떤 알고리즘의 상한선과 하한선이 같을 때는 Θ(Theta) 표기법을 사용

빅 오와 빅 오메가의 공통부분으로 최소와 최악의 중간인 평균적인 복잡도

 

Θ(n^2): 선택정렬

Θ(n log n): 병합정렬

Θ(n)

Θ(log n)

Θ(1)

 

https://www.boostcourse.org/cs112/joinLectures/41307

모두를 위한 컴퓨터 과학 (CS50 2019)

 

지금까지 소소하게 느낀점

알고리즘.. 너무 어려워... 어렵다.. 계속 해야 될 것 같다..

그래도 버블정렬 선택정렬 병합정렬 같은 용어는 기본적으로 이해할 수 있게 되었다..

성장했다.. 수고했다.. 이제 메모리를 공부해볼 시간..!