merge_sort(합병 정렬)[java]

merge_sort

개념

- 분할정복법을 사용하는 정렬이다.

분할정복법은 특정한 문제를 분할하고 그 부분을 정복하는 방법으로 문제를 해결한다.

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

위의 세가지 방식으로 merge_sort가 문제를 해결한다.

* 중요한 점은 문제를 분할할 때 작은 크기의 동일한 문제가 되므로 새로운 알고리즘을 만들 필요가 없다.

그림을 첨부해 보았다.... 그림에서 처럼 우선 배열의 원소가 하나가 될때까지 분할을 하고 원소가 하나인 배열부터 비교하며 합병을 한다. 분할과 합병 모두 크기만 작아지거나 커질 뿐 방법이 달라지는 것이 아니다. 따라서 divide알고리즘과 merge알고리즘만 만들고 그 알고리즘을 재귀적으로 호출하면 된다.

 

divide부분 코드

public static void mergeSort(int[] base,int p,int r){
        if(p<r){
            int mid = (p+r)/2;
            mergeSort(base,p,mid);
            mergeSort(base,mid+1,r);
            merge(base,p,r,mid);
        }
    }

- 배열을 두개로 나눠야하므로 mid라는 변수를 선언해 처음과 끝 값을 넣어주고 나눈 두개의 배열을 다시 호출한다.

- p<r일때만 가능하므로 배열의 원소가 1개일때까지만 가능하다.

- 배열의 원소가 1개가 되었을 때부터 차례대로 merge메소드를 호출한다.

 

** 주의 - 개념적으로 쉽게 하려고 배열의 원소가 하나라고 했지만 사실 하나의 배열을 가지고 가리키는 인덱스값을 바꿔준 것이므로 배열의 원소가 하나라는 것은 가리키는 값이 하나라는 것이다.

merge부분 코드

public static void merge(int[] base, int p,int r, int mid){
        int i = p;
        int j = mid+1;
        int k = i;
        tmp = new int[base.length];
        while(i<=mid && j<=r){
            if(base[i] < base[j]){
                tmp[k++] = base[i++];
            }else{
                tmp[k++] = base[j++];
            }
        }
        while(i<=mid){
            tmp[k++] = base[i++];
        }
        while(j<=r){
            tmp[k++] = base[j++];
        }
        for(i = p;i<=r;i++){
            base[i] = tmp[i];
        }
    }

- 하나의 배열을 가지고 가리키는 값만 바꾸는 것이므로 tmp라는 배열을 만들고 길이는 원래 배열의 길이만큼으로 잡는다.

- 처음 while문은 나눠진 두개의 배열 모두 아직 원소가 있을 때이다. 이때부터 두 배열의 앞의 값부터 비교하며 tmp배열을 채운다.

- 두 번째 while문과 세 번째 while문 모두 두개 중 하나의 배열을 다 쓴 경우다. 따라서 나머지 값들을 모두 tmp배열에 넣으면 된다.

- 마지막 for문 부분은 현재까지 정렬된 부분을 원래의 배열에 넣어주는 것이다.

 

merger_sort의 전체 코드

package sort;

import java.util.Arrays;

public class merge_sort {
    static int[] tmp;
    public static void main(String[] args) {
        int[] base = {5,2,4,7,1,3,2,6};
        mergeSort(base,0,base.length-1);
        System.out.println(Arrays.toString(tmp));
    }
    public static void mergeSort(int[] base,int p,int r){
        if(p<r){
            int mid = (p+r)/2;
            mergeSort(base,p,mid);
            mergeSort(base,mid+1,r);
            merge(base,p,r,mid);
        }
    }
    public static void merge(int[] base, int p,int r, int mid){
        int i = p;
        int j = mid+1;
        int k = i;
        tmp = new int[base.length];
        while(i<=mid && j<=r){
            if(base[i] < base[j]){
                tmp[k++] = base[i++];
            }else{
                tmp[k++] = base[j++];
            }
        }
        while(i<=mid){
            tmp[k++] = base[i++];
        }
        while(j<=r){
            tmp[k++] = base[j++];
        }
        for(i = p;i<=r;i++){
            base[i] = tmp[i];
        }
    }
}

 

merge_sort의 시간 복잡도

 

n개의 원소를 갖는 배열의 시간 복잡도는 결론부터 말하면 O(nlogn)이다.

T(n) = T(n/2) + T(n/2) + n 이렇게 표현할 수 있다.

여기서 T(n/2) = T(n/4) + T(n/4) + n/2 이렇게 쓸수 있는데

즉 T(n) = n + 2(n/2) + 4(n/4) ............. 2^k(n/2^k) + 2^n(n/2^n)이 된다.

n이 logn번 나오게 되고 따라고 시간 복잡도는 O(nlogn)이 된다