1. Introduction
- 알고리즘은 다양하게 선택가능하다.
- 예를들어 Insertion Sort는 Incremental method(증분 방법)을 사용한다.
- 이번 챕터에선 분할 정복(divide and conquer) 이라는 설계 방법을 간단하게 다루게 된다.
- 자세한 방법은 챕터 4때 알아보도록 하자.
2. Divide and Conquer(분할 정복)
- 많은 유용한 알고리즘들은 재귀적(recursive) 구조를 가지고 있음.
- 주어진 문제를 해결하기 위해, 이들은 스스로 한번 이상 호출하여 하위문제들을 해결함
- 일반적으로 분할 정복(Divide & Conquer)을 따름
- 문제를 원래 문제와 유사하지만 더 작은 크기의 여러 하위 문제로 나누고,
- 하위 문제를 재귀적으로 해결한 뒤 이러한 해결책들을 결합하여 원래 문제를 해결함
- 다음과 같이 3가지 Step으로 이루어져 있음
Step 1) 분할(Divide)
- 문제를 원래 문제와 유사하지만 더 작게 하위 문제로 나눔
Step 2) 정복(Conquer)
- 하위 문제를 재귀적으로 해결
Step 3) 결합(Combine)
- 하위 문제의 해결책들을 결합하여 원래 문제에 대한 해결책을 만듬
3. Merge Sort(병합정렬)
- Merge Sort(병합 정렬)은 분할 정복(Divide and Conquer)방법을 따른다.
- 전체 배열 A[1:n]에서 시작하여 하위 배열 A[p:r]를 정렬하고 점점 더 작은 하위 배열로 재귀적으로 내려감
- 다음은 Merge Sort가 작동하는 방식을 분할정복(Divide and Conquer)로 나타내보았다.
Step 1) 분할(Divide)
- 정렬할 하위 배열 A[p:r]을 두 개의 인접한 하위 배열로 나눈다. (각각의 크기는 절반)
- 이를 위해 A[p:r]의 중간점 q를 계산 (p와 r의 평균을 구하고 반올림)
- 그후 A[p:q] & A[q+1:r]로 하위 배열을 나눠준다.
cf) 배열의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
Step 2) 정복(Conquer)
- 각 하위 배열 A[p:q] & A[q+1:r]을 재귀적으로 Merge Sort(병합 정렬)을 사용해 정렬
Step 3) 결합(Combine)
- 두 정렬된 하위 배열 A[p:q] & A[q+1:r] 을 병합하여 다시 A[p:r]로 결합하여 정렬된 결과를 만든다.
-그림으로 나타내면 다음과 같다.
- 이를 파이썬 코드로 구현 해보자.
def merge_sort(arr,left,right):
if left>=right:
return
mid = (left+right)//2
merge_sort(arr,left,mid)
merge_sort(arr,mid+1,right)
return merge(arr,left,right)
def merge(arr,left,right):
tmp = []
mid = (left + right) //2
left_s, right_s = left, mid +1
while left_s <=mid and right_s <= right:
if arr[left_s] <= arr[right_s]:
tmp.append(arr[left_s])
left_s +=1
else:
tmp.append(arr[right_s])
right_s +=1
while left_s <=mid:
tmp.append(arr[left_s])
left_s+=1
while right_s <= right:
tmp.append(arr[right_s])
right_s +=1
for i in range(left,right+1):
arr[i] = tmp[i-left]
return arr
3.1. 병합정렬의 시간복잡도
- 즉 O(nlogn) 임을 알 수 있다.
4. Exercise
Q1) Merge_sort()를 이용하여 [3,41,52,26,38,57,9,49] 정렬하시오.
def merge_sort(arr,left,right):
if left>=right:
return
mid = (left+right)//2
merge_sort(arr,left,mid)
merge_sort(arr,mid+1,right)
return merge(arr,left,right)
def merge(arr,left,right):
tmp = []
mid = (left + right) //2
left_s, right_s = left, mid +1
while left_s <=mid and right_s <= right:
if arr[left_s] <= arr[right_s]:
tmp.append(arr[left_s])
left_s +=1
else:
tmp.append(arr[right_s])
right_s +=1
while left_s <=mid:
tmp.append(arr[left_s])
left_s+=1
while right_s <= right:
tmp.append(arr[right_s])
right_s +=1
for i in range(left,right+1):
arr[i] = tmp[i-left]
return arr
-------------------------------------------------
arr = [3,41,52,26,38,57,9,49]
merge_sort(arr,0,len(arr)-1)
[3, 9, 26, 38, 41, 49, 52, 57]
[Reference]
https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
'CS Study > CLRS (자료구조 | 알고리즘)' 카테고리의 다른 글
[CLRS] [3-1] 시간 복잡도 (big-O, big-Ω, big-θ) (0) | 2024.09.04 |
---|---|
[CLRS] [2-4] Bubble Sort(버블 정렬) (0) | 2024.09.04 |
[CLRS] [2-2] Analyzing algorithms (0) | 2024.09.02 |
[CLRS] [2-1] 삽입 정렬(Insertion sort)? (0) | 2024.09.01 |
[CLRS] [1-2] Algorithms as a technology (3) | 2024.09.01 |