병합정렬 Merge Sort * 반씩 계속 나눠 정렬하고 병합!!
병합정렬은 배열 계속 반으로 나누면서 왼쪽 반, 오른쪽 반 각각 정렬해서 합병하는 알고리즘이다. (분할 후 정복)
임시 저장을 위해 다른 배열이 하나 필요하다.
원 배열 A, 임시 배열 B
병합 정렬을 Top Down 방식(재귀)을 이용해 구현하면 다음과 같다.
Top Down 방식은 배열 윈소가 1개가 될 때까지 계속 쪼개는 방법이다.
public class Main
{
public static int[] arr2; // 임시 배열
public static void merge(int[] arr, int start, int mid, int end)
{ // 반쪽 두개 병합. 각각은 정렬되어 있음
arr2 = new int[end+1]; // 임시 배열의 크기는 원 배열과 같게
int index = start; // 임시배열의 인덱스
int i = start; // 왼쪽 배열의 시작
int j = mid+1; // 오른쪽 배열의 시작
while ((i <= mid) && (j <= end))
{
if (arr[i] <= arr[j])
{
arr2[index] = arr[i];
i++;
}
else
{
arr2[index] = arr[j];
j++;
}
index++;
}
if (i > mid) // 왼쪽 반 다 썼을 때
{
for (int k=j; k<= end; k++)
{
arr2[index] = arr[k];
index++;
}
}
else // 오른쪽 반 다 썼을 때
{
for (int k=i; k<= mid; k++)
{
arr2[index] = arr[k];
index++;
}
}
// 임시배열을 원 배열에 다시 넣음
for (int k=start; k<=end; k++)
arr[k] = arr2[k];
}
public static void mergeSort(int[] arr, int start, int end)
{ // 반쪽씩 정렬. 재귀 사용
if (start < end)
{
int mid = (start + end)/2;
mergeSort(arr, start, mid); // 왼쪽 반 정렬
mergeSort(arr, mid+1, end); // 오른쪽 반 정렬
merge(arr, start, mid, end); // 정렬 후 병합
}
}
public static void printArr(int[] arr)
{
for (int i=0; i<arr.length; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
public static void main(String[] args)
{
int[] arr = {91, 82, 13, 85, 68, 70, 98, 24};
printArr(arr);
mergeSort(arr, 0, arr.length-1);
printArr(arr);
}
}시간 복잡도는 O(NlogN)이다. 배열을 쪼개는 과정에서 8 -> 4 -> 2 -> 1 식으로 쪼개지기 때문에 그 높이는 O(logN)이다. 각 단계에서 병합 시 모든 값을 비교해야 하므로 O(N)의 시간이 필요하다.
Bottom Up방식은 1개씩, 2개씩, 4개씩 정렬을 반복하는 방법이다. 각각 원소 하나가 정렬된 배열이라 생각.
구현하면 다음과 같다. - merge는 같고 mergeSort만 변경.
public static void mergeSort(int[] arr, int end)
{
int size = 1; // size는 1,2,4,8,16... 반쪽 씩 합쳐지면서 두배로 커짐
while (size <= end)
{
for (int i=0; i<=end-size; i=i+2*size)
{
int high = Math.min(i+2*size-1, end);
merge(arr, i, i+size-1, high);
}
size*=2;
}
}
public static void main(String[] args)
{
int[] arr = {91, 85, 68, 70, 98, 24, 1,2,3,4,9};
printArr(arr);
mergeSort(arr, arr.length-1);
printArr(arr);
}마찬가지로 시간 복잡도는 O(NlogN)이다.
병합 정렬은 입력과 같은 크기의 임시 배열이 필요하기 때문에 공간 복잡도는 O(N)이다.
분할 정복을 이용해 O(nlogn)의 시간에 주어진 배열에서 중복을 제거하는 문제가 주어졌을 때 Merge Sort를 이용해 해결할 수 있다.
기본 Merge Sort의 Merge 메서드는 다음과 같다.
while ((i <= mid) && (j <= end))
{
if (arr[i] <= arr[j])
{ // 왼쪽 반의 원소가 더 작거나 같다면 왼쪽 원소를 arr2에 넣음
arr2[index] = arr[i];
i++;
}
else
{ // 오른쪽 반의 원소가 더 작다면 오른쪽 원소를 arr2에 넣음
arr2[index] = arr[j];
j++;
}
index++;
}이것을 다음과 같이 바꾸면 중복 원소를 제거할 수 있다.
while ((i <= mid) && (j <= end))
{
if (arr[i] < arr[j])
{ // 왼쪽 반의 원소가 더 작다면 왼쪽 원소를 arr2에 넣음
arr2[index] = arr[i];
i++;
}
else if (arr[i] > arr[j])
{ // 오른쪽 반의 원소가 더 작다면 오른쪽 원소를 arr2에 넣음
arr2[index] = arr[j];
j++;
}
else // 양쪽 원소가 같을 때
{ // arr2에 원소 넣지 않고 한쪽 인덱스만 증가시킴
i++; // j++ 해도 됨.
}
index++;
}