[Algorithm] Merge Sort (합병 정렬)

분할 정복법 (Divide and Conquer)

아래 3가지 단계를 거쳐서 어떤 문제를 해결하는 기법

Merge Sort와 Quick Sort에서 사용하는 기법

• 분할(Divide) : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
• 정복(Conquer) : 각각의 작은 문제를 순환적으로 해결
• 합병(Merge): 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

Merge Sort

Step 1) Divide - 데이터가 저장된 배열을 절반으로 나눔

Step 2) Recursively sort - 각각을 순환적으로 정렬

Step 3) Merge - 정렬된 두 개의 배열을 합쳐 전체를 정렬

Step 3인 Merge 과정 자세히 보기 

- 정렬된 두 배열을 Merge하는 과정

- 새로운 추가 배열 필요

- i(첫번째 list에서 가장 작은 값), j(두번째 list에서 가장 작은 값), k(추가 list에서 가장 작은 값) 변수 필요

 

1. A[i]와 A[j]를 비교하여 작은 값을 추가 배열에 추가

2. 작은 값에 속한 인덱스 올림. i++ or j++ , k++

3. i or j가 해당 배열의 인덱스보다 크다면 다른 배열의 값은 그대로 추가배열에 추가 해주면 됨!

소스

// 재귀 함수이므로 매개변수 명시화 필요
public void mergeSort(int[] arr, int p, int r) {		
	if (p < r) {
		int q = (p+r) / 2;		// 1. p와 r의 중간 지점 계산
		mergeSort(arr, p, q);	// 2. 전반부 정렬
		mergeSort(arr, q+1, r);	// 3. 후반부 정렬
		merge(arr, p, q, r);	// 4. 합병
	}
}

/* Merge Business Logic - 정렬되어 있는 두 배열 arr[p...q]와 arr[q+1...r]을 합하여 
 * 정렬된 하나의 배열 arr[p...r]을 만듦. 
 * arr[p... q] arr[q+1...r] => 정렬되어 있는 두 배열 
 * arr[p.................r] => 정렬된 하나의 배열을 만드는 작업 : Merge
 */
public void merge(int[] arr, int p, int q, int r) {
	int i=p, j=q+1, k=p;
	int[] temp = new int[arr.length];
	
	// 각각 i, j가 각 배열의 길이를 넘지 않는다면 비교하여 temp에 넣어주기 
	while(i <= q && j <= r) {
		if (arr[i] <= arr[j]) {
			temp[k++] = arr[i++];
		} else {
			temp[k++] = arr[j++];
		} 
	}
	
	// 첫번째 배열에 있는 나머지 값들은 이미 정렬된 데이터들이므로 차례대로 temp 배열에 넣어주면 됨. 
	while (i <= q) {
		temp[k++] = arr[i++];
	}
	
	// 두번째 배열에 있는 나머지 값들은 이미 정렬된 데이터들이므로 차례대로 temp 배열에 넣어주면 됨. 		
	while(j <= r) {
		temp[k++] = arr[j++];
	}
	
	// index p부터 r까지 원래 배열에 값 넣기 
	for (int l = p; l <= r; l++) {
		arr[l] = temp[l];
	}
	
	print(arr);
}

 

시간복잡도 T(n) = O(nlogn)

if n = 1      -> 0

otherwise -> T(n/2) + T(n/2) + n = 2T(n/2) + n

 

Merge sort 시간복잡도

 

 

 

 

 

 

Ref. https://www.youtube.com/watch?v=2YvFRAC8UTM