[자료구조] 병합정렬(MergeSort) with JAVA

[자료구조] 병합정렬(MergeSort) with JAVA

 

* 병합정렬이란?

 병합 정렬은 여러 개의 정렬된 자료의 집합을 결합해 하나의 집합으로 만드는 정렬 방법이다. 이 정렬은 전체를 상대로 수행하지 않고 분할(Divide)한 뒤 각 부분집합들에 대해 정렬한 후 다시 결합(Combine)하는 분할 정복(Divide and Conquer) 기법을 사용한다.

 

* 2-way병합과 n-way 병합

 2개의 정렬된 집합을 하나의 집합으로 만드는 병합 방법을 2-way 병합이라고 하고 n개의 정렬된 집합을 결합하여 하나의 집합으로 만드는 방법을 n-way 병합이라고 한다.

 

* 2-way병합 정렬 방법

 1) 분할(Divide) : 자료들을 같은 크기의 2개의 부분 집합으로 분할한다.

 2) 정복(Conquer) : 부분 집합의 내에 있는 원소들을 정렬한다. 부분 집합의 크기가 충분히 작지 않다면 순환호출을 활용해 더욱 작게 분해한다.

 3) 결합(Combine) : 정렬된 부분집합들을 하나로 결합한다.

 

* 예시

 정렬되지 않은 집합 {58,8,28,3,18,6,33,20}의 자료들을 MergeSort를 이용해 정렬한다.

 1. 분할 단계 : 정렬할 자료 집합에 대해 최소 원소의 부분집합(1개)이 될 때까지 분할 작업을 반복한다. 즉, 8개의 부분집합을 만든다.

 

58

8

28

3

18

6

33

20

 

이것을 순환호출을 활용해 각각 (4개, 4개), (2개, 2개, 2개, 2개), (1개, 1개 .. 1개) 이런 식으로 쪼갠다.

 

 2. 병합 단계 : 2개의 부분집합을 하나의 집합으로 정렬하며 병합한다. 8개의 부분집합이 1개로 병합될 때까지 반복한다.

 

3

6

8

18

20

28

33

58

 

[참조] C로 배우는 쉬운 자료구조, 한빛미디어, 이지영 저

 

* 병합정렬(MergeSort) JAVA 코드 

package Sort;
 
import java.util.Arrays;
 
 
public class MergeSort {
    static int[] sorted = new int[8];
    public static void merge(int a[], int m, int middle, int n) {
        int i = m;             // 첫 번째 부분집합의 시작 위치 설정
        int j = middle+1;     // 두 번째 부분집합의 시작 위치 설정
        int k = m;             // 배열 sorted에 정렬된 원소를 저장할 위치 설정
        
        while(i<=middle && j<=n) {
            if(a[i]<=a[j]) {
                sorted[k] = a[i];
                i++;
            }else {
                sorted[k] = a[j];
                j++;
            }
            k++;
        }
        if(i>middle) {
            for(int t=j;t<=n;t++,k++) {
                sorted[k] = a[t];
            }
        }else {
            for(int t=i;t<=middle;t++,k++) {
                sorted[k] = a[t];
            }
        }
        
        for(int t=m;t<=n;t++) {
            a[t] = sorted[t];
        }
        System.out.println("병합 정렬 후: "+Arrays.toString(a));
    }
        
    
    public static void mergeSort(int a[], int m, int n) {
        int middle;
        if(m<n) {
            middle = (m+n)/2;
            mergeSort(a, m, middle);    // 앞 부분에 대한 분할 작업 수행
            mergeSort(a, middle+1, n);    // 뒷 부분에 대한 분할 작업 수행
            merge(a, m, middle, n);        // 부분집합에 대하여 정렬과 병합 작업 수행
        }
    }
    public static void main(String[] args) {
        int[] list = {58,8,28,3,18,6,33,20};
        int size = list.length;
        System.out.println("정렬 수행 전: "+Arrays.toString(list));
        System.out.println("-----------------병합 정렬 수행 시작------------------");
        mergeSort(list, 0, size-1);
    }
 
}