분할 정복 알고리즘 , 합병정렬(Merge Sort) 알고리즘 자바 코드

 

주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘
분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며
이들의 해를 취합하여 원래의 문제를 얻기위해 사용한다.

부분문제
> 분할된 입력에 대한 문제 (SubProblem)

부분해
 > 부분문제의 해

더 이상 분할 할 수 없을때 까지 부분문제를 계속해서 분할한다.

정복과정
 > 부분해를 취합하면서 구하고자 하는 원래 문제의 답을 얻는다.

 

크기가 N인 입력에 대한 분할정복 알고리즘

첫번째 나누어진 각각의 크기에 대한 입력은 n/2

두번째 나누어진 각각의 크기에 대한 입력 n/4

.
.
.

더 이상 입력의 크기를 나눌 수 없는 경우 (1인경우) 까지 문제의 수준을 쪼개는 과정을 분할 과정이라고 한다.

 

입력의 크기가 N일때 총 분할 횟수의 일반화 과정
> 문제를 두부분으로 나누고 각각의 부분에는 절반씩인 N/2씩 들어가는 경우 분할의 횟수를 k라고 할때

1번째 분할 후 각각의 입력의 크기 N/2^1

2번째 분할 후 각각의 입력의 크기 N/2^2

3번째 분할 후 각각의 입력의 크기 N/2^3

.
.
.

k번째 분할 후 각각의 입력의 크기는 N/2^k가 된다.

여기서 N/2^k = 1이 되어야 하므로 ( 더 이상 분할 할 수 없는 경우 == 입력의 크기가 1이 되는경우 )

분할 횟수 k는 log2(N)이 된다. (밑이 2인 로그)

k = log2(N)

분할과정이 log(n)인만큼 빠른 탐색이 가능

 

정복과정

> 문제의 크기가 1이 될때까지 분할한 다음 해를 찾기위해 취합 과정
> 단순 분할만 해서는 해를 구할 수 없으며 분할된 부분문제들을 정복해야 한다. (subsolution)

합병정렬 (Merge Sort)
> 문제가 2개로 분할되고, 부분문제의 크기가 1/2로 감소하는 알고리즘

• n 개의 숫자들을 n/2개씩 2개의 부분문제로 분할
• 각각의 부분문제를 재귀적으로 합병정렬
  > 1이 될때까지 재귀적으로 문제를 계속해서 분할해 나감
• 2개의 정렬된 부분을 합병하여 정렬 (합병 과정이 문제를 정복)
  > 처음 입력된 데이터의 크기가 될때까지 계속해서 합병해서 정렬

MergeSort(A,p,q) // 합병정렬 함수 정의
A : 정렬해야되는 배열
p,r : 시작위치, 끝 위치 (index 값)

입력된 데이터 : A[p] ~ A[r]
출력된 데이터 : 정렬된 A[p] ~ A[r]

1. 정렬할 부분의 원소의 수가 2개 이상일 때에만 다음 단계 수행, 
   만일 n = 1이면 그 자체로 정렬된 것이므로 어떤 수행을 할 필요 없이 이전 호출 했던 곳으로 리턴
2. 정렬할 부분의 원소들을 1/2로 나누기 위해 q = (p+r)/2 (소수점 버림)
3. MergeSort(A,p,q)와 MergeSort(A,q+1,r)를 재귀호출 하여 각각 정렬
4. 각각 정렬된 부분을 합병
5. 합병 과정에서 마지막에 임시 배열에 있는 합병된 원소들을 배열 A로 복사

ex) 합병정렬 자바 코드

import java.util.Arrays;
import java.util.Random;

public class MergeSort {

    public static void mergeSort(int[] data, int p, int r){
        int q; // 중간값
        if (p < r){ // 배열의 원소의 수가 2개 이상이라면
            q = (p+r)/2; // 소수점 내림
            mergeSort(data, p, q); //절반
            mergeSort(data, q+1, r); // 남은 절반
            merge(data, p, q, r); // 합병 수행
        }
    }

    public static void merge(int[] data, int p, int q, int r){ // 합병을 수행하는 과정 시작, 중간, 마지
        int i = p; // 시작위치
        int j = q+1; // 중간다음
        int k = p; // 시작위치

        int[] temp = new int[data.length]; // 새로운 임시저장공간

        while (i <= q && j <= r){
            if (data[i] <= data[j]){
                temp[k++] = data[i++];
            }
            else{
                temp[k++] = data[j++];
            }
        }

        while(i <= q){ temp[k++] = data[i++]; }
        while(j <= r){ temp[k++] = data[j++]; }

        for (int a = p; a <= r; a++){
            data[a] = temp[a];
        }
    }

    public static void main(String[] args){
        Random r = new Random();
        int size = 10000;
        System.out.println("입력된 데이터의 크기 : " + size);

        int[] data = new int[size];

        for (int i = 0; i < size; i++) {
            data[i] = r.nextInt(100);
        }

        System.out.println("정렬 전 데이터");
        for (int i : data){ // 정렬 전 데이터 출력
            System.out.printf("%d ", i);
        }

        long start = System.currentTimeMillis();

        mergeSort(data,0,data.length -1 ); // 데이터 병합 정렬

        long end = System.currentTimeMillis();
        double total = ((double)end - (double)start)/100;
        
        System.out.println("\n정렬 후 데이터");
        for (int i : data){
            System.out.printf("%d ", i);
        }

        System.out.println("합병정렬 걸린시간 : " + total + "초");

    }
}

 

데이터 크기가 8인경우 정렬과정에 대한 설명 

 

합병정렬의 시간복잡도

• 분할하는 부분은 배열의 중간 인덱스 계산과 2번의 재귀 호출이므로 O(1)
• 합병의 수행 시간은 입력의 크기에 비례
  > 2개의 정렬된 배열의 크기가 각각 m과 n이라면 시간복잡도 O(m+n)
  > 각 층에서 수행된 비교 횟수 O(n)
• 최종 합병정렬의 시간복잡도 = (층수) X O(n) = log2(n) X O(n) = O(n*logn)