합병정렬 알고리즘 요약
합병 정렬은분할정복 알고리즘 중 하나 라고 볼 수 있습니다.
-
그럼 분할정복 알고리즘이란 무엇인가?
문제를 두 개의 작은 문제로 쪼개고, 나눈 두 문제를 해결시도한다. 만약 해결이 안된다면 다시 두개의 작은 문제로 쪼개고, 나눈 문제에 대하여 해결시도한다. ...이렇게 반복되는 문제해결방법을분할정복 알고리즘이라고 합니다. -
합병정렬 알고리즘의 대략적인 과정
리스트 길이가 0 또는 1이면 이미 정렬된 것으로 인식합니다. 그렇지 않은 경우에는 정렬되지 않은 리스트라고 인식합니다. 리스트를 절반으로 잘라 두 개의 리스트로 나누고 각 부분 리스트에 대해 재귀적으로 합병정렬을 이용해 정렬합니다. 정렬된 부분 리스트들을 하나의 리스트로 합병합니다.
합병 정렬 알고리즘이란 것이 구체적으로 무엇인지
하나의 리스트를 두 개의 같은 크기인 부분 리스트로 나누고 이를 각각 정렬한다음 다시 하나의 리스트로 합쳐 전체가 정렬된 리스트가 되게 하는 방법입니다.
합병정렬 알고리즘에는 다음의 단계로 이뤄져있습니다.
- 분할의 개념 : 입력된 배열을 두 개의 부분 배열로 나눕니다.
- 정복의 개념 : 부분 배열을 정렬합니다. 하지만 만약 배열의 크기가 작지 않다면 순환호출을 통해 분할정복을 적용합니다.
- 결합의 개념 : 정렬된 부분 배열들을 하나의 배열로 합칩니다.
합병 정렬 알고리즘의 예시
만약 처음 배열에 26,9,11,19,24,12,14,20이 저장되어있다고 해봅시다. 문제로 이 배열을 오름차순 정렬을 하라고 제시되어있다고 해봅시다. 이를 합병정렬을 이용해보면 다음과 같을것입니다.
- 두 개의 정렬된 리스트를 합병하는 과정
두 개 리스트 값들을 하나씩 값들을 처음부터 비교->더 작은 값들 새 리스트에 옮깁니다. 만약 두 리스트 중 하나가 끝나면 나머지 리스트 값들을 모두 새 리스트(sorted된 리스트)로 복사하고 원래의 리스트(list)로 옮깁니다.
[26,9,11,19,24,12,14,20]이 배열을 두 개의 부분 리스트로 쪼갭니다.
[26, 9, 11, 19] [24, 12, 14, 20]두 개의 배열을 네 개의 부분 배열로 쪼갭니다.
[26, 9] [11, 19] [24, 12] [14, 20]이 배열들을 두 개의 배열로 쪼갭니다.
[26] [9] [11] [19] [24] [12] [14] [20]더이상 쪼갤 배열이 없으므로 두 개의 배열씩 합치고, 정렬도 시켜줍니다.
[9, 26] [11, 19] [12, 24] [14, 20]또 다시 두 개의 배열씩 합치고 정렬도 시켜줍니다.
[9, 11, 19, 26] [12, 14, 20, 24] 마지막도 마찬가지로 크기순으로 선택해 나갑니다.
[9, 11, 12, 14, 19, 20, 24, 26]최종적으로 정렬된 배열을 받아볼 수 있습니다.
합병 정렬 알고리즘의 총 복잡도
전반적인 반복의 수는 8->4->2->1 로 배열의 크기가 작아지므로 O(logN)의 시간이 필요하고 병합마다 모든 값들을 비교해야하므로 O(N)의 시간이 필요합니다. 따라서 총 시간 복잡도는 O(NlogN)이 됩니다.
배열을 추가로 생성해야하고 차지해야하는데 이에 들어가는 공간 복잡도는 O(N)입니다. 총 원소의 갯수만큼 리스트를 생성해야하기 때문입니다.
이를 재귀(자바)로 표현하면 다음과 같습니다. TOP-DOWN방식의 구현
아래의 코드는 https://st-lab.tistory.com/233 의 작성자님의 코드를 참고하였습니다.
public class MergeSort{
public static void mergeSort(int []arr){
sort(arr, 0, arr.length-1);
}
static void sort(int[] arr, int left, int right){
if(left == right) return;
/**
원소가 하나인 경우 리턴합니다.
*/
int mid = (left+right)/2;
sort(arr, 0, mid); //왼쪽 부분 배열
sort(arr, mid+1, right); // 오른쪽 부분 배열
merge(arr, left, mid, right); // 위 두 부분 배열을 합칩니다(정렬도 함께)
}
private static void merge(int[] arr, int left, int right){
int l = left; //왼쪽 부분 리스트의 시작점 지정
int r = mid+1; // 오른쪽 부분 리스트의 시작점 지정
int idx = left; //채워넣을 배열 인덱스
while(l<=mid && r<=right){
if(a[l]<=a[r]){
sorted[idx] = a[l];
idx++;
l++;
}
/**
왼쪽 부분 리스트의 l번째 원소가 오른쪽 부분 리스트의 r번째 원소보다 작거나 같은 경우 왼쪽 l번째 원소를 새 배열에 넣고 l, idx값을 1 증가시킵니다.
*/
else(a[r]<=a[l]){
sorted[idx] = a[r];
idx++;
r++;
}
/**
오른쪽 부분 리스트의 r번째 원소가 왼쪽 부분 리스트의 l번째 원소보다 작거나 같은 경우 오른쪽 r번째 원소를 새 배열에 넣고 r, idx값을 1 증가시킵니다.
*/
if(l>mid){
while(r<=right){
sorted[idx]=a[r];
idx++;
r++;
}
}
/**
왼쪽 부분 리스트가 먼저 모두 새 배열에 채워진 경우, 오른쪽 부분 리스트 나머지 원소를 새 배열에 채워줍니다.
*/
else{
while(l<=mid){
sorted[idx]=a[l];
idx++;
l++;
}
for(int i=left;i<=right;i++){
a[i] = sorted[i];
}
/**
정렬된 배열을 기존 배열에 복사합니다.
*/
}
}
}
