병합정렬(mergeSort)
주어진 크기가 n인 리스트 A를 크기가 n/2인 두 부분으로 나눈다.
크기가 n/2인 두 부분을 재귀적으로(recursively) 정렬한다.
정렬된 두 부분을 하나로 병합한다
Merge(병합) 알고리즘 :
나뉜 두부분의 첫부분을 비교하여 작은 원소를 새로운 배열에 넣어주고, 작은 원소가 있던 부분배열의 인덱스를 늘려준다.
이렇게 부분배열이 다 넣어질 때까지 반복한다.
다른 한쪽부분은 남은 부분이 있을 수 있으므로 남은 부분배열의 전체를 배열에 넣어준다.
Pseudo-code
mergeSort 함수 : 정렬되지 않은 리스트(배열)을 재귀적으로 분할하는 역할을 한다
Algorithm mergeSort(arr, left, right)
if (left < right)
mid = (first + right) / 2
mergeSort(arr, left, mid)
mergeSort(arr, mid+1, right)
merge(arr, left, mid, right)
merge 함수 : 분할된 리스트(배열)을 병합(합병)하는 역할을 한다.
Algorithm merge(arr, left, right)
i = 0 //left_list의 인덱스
j = 0 //right_list의 인덱스
k = 0 //merge_list의 인덱스
while(i < len(left_list) and j < len(right_list))
if left_list[i] <= right_list[j]
merge_list[k] = left_list[i]
i += 1
else
merge_list[k] = right_list[j]
j += 1
k+=1
if (i < len(left_list))
for i to len(left_list) - 1
merge_list[k] = left_list[i]
k += 1
if (j < len(right_list))
for j to len(right_list) - 1
merge_list[k] = right_list[j]
k += 1
Python
리턴값 존재
def merge_sort(list):
if len(list) <= 1: # base case: 리스트에 원소가 하나 밖에 없을 때
return list
mid = len(list) // 2 # 리스트의 중간지점
left_list = list[:mid] # 리스트의 왼쪽 부분
right_list = list[mid:] # 리스트의 오른쪽 부분
left_list = merge_sort(left_list) # 재귀함수를 호출하여 다시 나눈다.
right_list = merge_sort(right_list)
return merge(left_list, right_list) # 왼쪽부터 오른쪽으로 merge
def merge(left, right):
i = 0
j = 0
merge_list = []
while i < len(left) and j < len(right): # left, right 가 아직 남아있을 때
if right[j] < left[i]:
merge_list.append(right[j])
j += 1
else:
merge_list.append(left[i])
i += 1
if (i < len(left)): # left 만 남아있을 때, 리스트에 리스트를 합친다.
merge_list += left[i:len(left)]
else:
merge_list += right[j:len(right)]
return merge_list
Java
public class MergeSort{
public void mergeSort(int[] arr, int left, int right){
if(left < right){
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right)
merge(arr, left, mid, right)
}
}
public void merge(int[] arr, int left, int mid, int right){
//두 부분배열의 사이즈 찾기
int n1 = mid - left + 1 ;
int n2 = right - mid;
//mid를 기준으로한 부분배열
int left_list[] = new int[n1];
int right_list[] = new int[n2];
//배열값 넣기
for (int i = 0; i < n1; i++) {
left_list[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
right_list[j] = arr[mid + 1 + j];
}
//merge
//초기 인덱스
int i = 0;
int j = 0;
// 병합된 배열의 초기 인덱스
int k = left;
// L 사이즈만 큼 loop (L배열 초기 인덱스 < L배열 사이즈)
// R 사이즈만 큼 loop (R배열 초기 인덱스 < R배열 사이즈)
while (i < n1 && j < n2) {
// L 배열의 값 <= R배열의 값
if (L[i] <= R[j]) {
// L값 arr에 담아주기
arr[k] = L[i];
//L 을 담아주었으니 L의 인덱스 증가
i++;
}else {
// L 배열의 값 > R배열의 값
// R값 arr에 담아주기
arr[k] = R[j];
//R 을 담아주었으니 R의 인덱스 증가
j++;
}
k++;
}
//L에 남은 값이 있다면 복사
while(i < n1) {
arr[k] = L[i];
i++;
k++;
}
//R에 남은 값이 있다면 복사
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
}
수행시간분석
T(n) = 1 (if n == 1)
= 2T(n/2) + cn (if n > 1)
(c는 상수)
T(n/2) = 2T(n/2^2) + cn/2
T(n) = 2(2T(n/2^2) + cn/2) + cn = 2^2(T(n/2^2)) + cn + cn
...
T(n) = 2^k(T(n/2^k)) + kcn
n/2^k = 1
k = log n 일 때,T(n) = nT(1) + cnlog n
T(n) = O(nlog n)
'Algorithm' 카테고리의 다른 글
[알고리즘] binarySearch 이진탐색, 재귀이진탐색_분할과 정복 (pseudo-code 파이썬, Java) (0) | 2021.10.16 |
---|---|
[알고리즘]분할과 정복 개념 및 예시 (0) | 2021.10.15 |
[알고리즘] bubble_sort 버블정렬(pseudo-code, 파이썬, Java) (0) | 2021.10.15 |
[알고리즘] selectionSort 선택정렬(pseudo-code, Java, 파이썬) (0) | 2021.10.14 |
[알고리즘] Stable & In-place (0) | 2021.10.14 |