정렬 알고리즘 - 합병 정렬

합병 정렬 (Merge Sort)

분할 정복법

- 분할정복법은 본질적으로 순환 함수를 사용하여 문제를 해결하려 한다.

- 분할 : 해결하려하는 문제를 작은 크기의 동일한 문제들로 분할한다.

- 정복 : 각각의 작은 문제를 순환적(Recursion)으로 해결한다.

- 합병 : 작은 문제의 해를 합하여(Merge) 원래 문제애 대한 해를 구한다.

합병 정렬

- 데이터가 저장된 배열을 절반 나눈다.

- 각각을 순환(Recursion)방식으로 정렬한다.

- 정렬된 두 개의 배열을 합쳐 전체를 정렬한다.

- 합병 정렬의 진행 과정

- 분리된 두 배열을 병합

- 이미 i배열과 j배열은 정렬이 되어있는 상태이고 k배열에 두 배열을 합치기 위해서는 작은 순서대로 넣어주어야 한다.

- i와 j배열의 가장 작은 원소들끼리 비교하여 더 작은 원소를 k배열에 넣은 다음 해당 배열의 인덱스와 k배열의 인덱스를 1상승시키는 과정을 반복하여 두 배열을 합치게 된다.

- 슈도 코드

mergeSort (A[], p, r) {//A[p ~ r]을 정렬한다.

if (p < r) then {

q <- (p + r) / 2; //p와 q의 중간 지점을 계산한다.

mergeSort (A, p, q); //중간지점을 기준으로 전반부를 정렬한다.

mergeSort (A, q + 1, r); //후반부를 정렬한다.

merge (A, p, q, r); //정렬된 전반부와 후반부를 병합하여 온전하게 정렬된 배열을 완성한다.

}

}

merge (A[], p, q, r) {

정렬된 두 배열 A[p ~ q]와 A[q + 1 ~ r]을 서로 합하여 정렬된 하나의 배열 A[p ~ r]을 만든다.

}

- 시간 복잡도

T(n) = $\begin{cases}0&if (n = 1)\\T(\left\lceil n/2 \right\rceil )+T(\left\lfloor n/2\right\rfloor)+n&otherwise\end{cases}$

∴ T(n) = 2T($\frac {n}{2}$) + n = O($n\log {n}$)

- T([n / 2]하는 과정을 두 번 거쳐 나뉜 두 배열을 정렬한 후 두 배열을 합치는 n의 시간이 걸린다.

- 구현

void merge (int data[], int p, int q, int r) {

int i = p, j = q + 1, k = p;

int tmp[data.length()];

while (i <= q && j <= r) {

if (data[i] <= data[j])

tmp[k++] = data[i++];

else

tmp[k++] = data[j++];

}

while (i <= q) //데이터가 앞쪽에 남았을 경우 실행

tmp[k++] = data[i++];

while (j <= r) //데이터가 뒤쪽에 남았을 경우 실행

tmp[k++] = data[j++];

for (int i = p; i <= r; i++)

data[i] = tmp[i];

}

-> 데이터를 정렬할 때 tmp라는 추가적인 저장 배열이 필요하다는 것이 합병 정렬의 유일한 흠이라고 할 수 있다.

코드 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
//2019-05-27
//Recursive방식으로 프로그래밍하였다.
//시작점과 끝점을 잘못 설정하여 ArrayOutOfBoundException이 계속 나와 해결에 시간을 소요했다.
//sort함수를 호출할 때 시작점을 1로 지정함으로써 중간점 등 모든 것을 해결할 수 있었다.
public class MergeSort {
    static BufferedWriter bw;
    static int[] inputArray;
    
    public static void main(String[] args) throws Exception {
        init();
        sorting(inputArray, 1, inputArray.length);
        printArray(inputArray);
    }
    
    static void init() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        bw.write("정렬하고자 하는 수를 입력해주세요 : ");
        bw.flush();
        
        int index = 0;
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
        inputArray = new int[st.countTokens()];
        
        while (st.hasMoreTokens())
            inputArray[index++] = Integer.parseInt(st.nextToken());
    }
    
    static void printArray(int[] array) throws Exception {
        bw.write("정렬된 결과값은 " + Arrays.toString(array) + "입니다.");
        bw.close();
    }
    
    static void sorting(int[] inputArray, int start, int end) {
        int middle;
        
        if (start < end) {
            middle = (start + end) / 2;
            sorting(inputArray, start, middle);
            sorting(inputArray, middle + 1, end);
            merge(inputArray, start, middle, end);
        }
    }
    
    static void merge(int[] data, int start, int middle, int end) {
        int i = start - 1, j = middle, k = start - 1;
        int[] tmp = new int[data.length];
        
        while (i <= middle - 1 && j <= end - 1) {
            if (data[i] <= data[j])
                tmp[k++] = data[i++];
            else
                tmp[k++] = data[j++];
        }
        
        while (i <= middle - 1)
            tmp[k++] = data[i++];
        while (j <= end - 1)
            tmp[k++] = data[j++];
        
        for (int index = start - 1; index <= end - 1; index++)
            data[index] = tmp[index];
    }
}