알고리즘: Mergesort 합병 정렬

4. Sorting

4-3. Mergesort 합병 정렬

• 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것
• 입력 데이터가 많으면서 자주 정렬해야 할 필요가 있을 때 사용.
• 정렬 문제의 문제 복잡도 F(n) = O(n lgn) time
• 합병 정렬의 worst case complexity W(n) = O(n lgn) time
• W(n) = F(n) : Optimal algorithm
• 따라서 합병 정렬 알고리즘은 Optimal algorithm 이다.

 

Merging Sorted Sequences

Problem

오름차순으로 정렬된 두 리스트 A, B를 새로운 리스트 C로 합친다.

 

Strategy

C의 첫 번째 item ☞ A와 B의 첫 번째 항목 중 더 작은 값.

• A와 B 두 개의 리스트의 요소들을 처음부터 하나씩 비교하여 두 개의 리스트의 요소 중 더 작은 요소를 C로 옮긴다.
• 둘 중 하나가 끝날 때까지 이 과정을 되풀이한다.
• 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 요소들을 전부 새로운 리스트 C로 복사한다.
• 리스트 C의 size는 A의 size + B의 size

 

Algorithm: Merge 합병

Merge(A, B, C)
if (A is empty)			//A가 비었다면 C에 B의 남은 모든 원소 채워주기(비교연산 수행X)
	rest of C = rest of B
else if (B is empty)		//B가 비었다면 C에 A의 남은 모든 원소 채워주기(비교연산 수행X)
	rest of C = rest of A
//비어 있지 않으면 비교 연산 수행해서 더 작은 값을 C에 채우기
else if (first of A ≤ first of B)		//A의 첫 원소가 B의 첫 원소보다 작거나 같을 때
	first of C = first of A			//C에 A의 첫 원소 채워넣기
	Merge (rest of A, B, rest of C)		//재귀
else						//A의 첫 원소가 B의 첫 원소보다 클 때
	first of C = first of B			//C에 B의 첫 원소 채워넣기
	Merge (A, rest of B, rest of C)		//재귀
return

 

W(n) = n - 1 ∈ θ(n) time

              ↳ - 1은 마지막 원소. 마지막 원소는 비교할 원소가 없기 때문에 별도의 연산 없이 바로 C에 복사한다. 따라서 마지막 원소에서는 비교연산이 일어나지 않는다.

 

Using Divide and Conquer: Mergesort

Mergesort Strategy: devide and conquer(분할과 정복)

devide and conquer(분할과 정복 기법)

• 문제를 2개의 작은 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략.
• 분리된 문제가 아직도 해결하기 어렵다면, 즉 충분히 작지 않다면 분할 정복 방법을 연속해서 다시 적용한다.
• 대개 순환 호출을 이용하여 구현된다.

 

Mergesort의 devide and conquer 단계

1. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
2. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

Algorithm: Mergesort 합병정렬

Input: 배열 E와 indexe 2개: first, last. 원소 E의 인덱스 i는 first ≤ i ≤ last의 범위 내에서 존재한다.

Output: E[first], …, E[last]는 동일한 entry들의 재배열로 정렬된다.

void mergeSort(Element[] E, int first, int last)
if (first < last)
	int mid = (first+last)/2;
	mergeSort(E, first, mid);
	mergeSort(E, mid+1, last);
	merge(E, first, mid, last);
return;

 

 

합병정렬의 복잡도

W(n) = W(n/2) + W(n/2) + Wmerge(n) ∈ θ(n log n)

• Wmerge(n) = n-1
• W(1) = 0 ☞ 원소 갯수가 하나일 때 수행시간. 이미 정렬 돼 있으므로 연산이 필요 없음.

 

---

자료 출처

• Computer Algorithms (Sara Baase, Allen Van Gelder저, Addison Wesley, 2000)
• 위키백과 분할 정복 알고리즘
• C언어로 쉽게 풀어쓴 자료구조 (천인국 외 2인 저, 생능출판, 2005)

 

참고하면 좋을 블로그

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog