병합정렬 (Merge Sort)

 

| 병합정렬(Merge Sort)

• 대표적인 분할정복 방법을 채택한 알고리즘 이다.
• 퀵 정렬과 동일하게 O(N * logN)의 시간 복잡도를 가진다.
• 병합정렬은 정확히 반씩 나눈다는 점에서 최악의 경우에도 O(N * logN)을 보장한다.

• 하나씩 나누고 합쳐지면서 정렬을 수행한다.
• 즉, 합쳐지는 순간에 정렬을 수행한다.

• 왼쪽 집합의 i와 두번째 집합의 j를 증가시키면서 비교연산을 통해 비어있는 새로운 배열에 넣어준다.
• 병합정렬을 구현할 때 중요한 부분은 반드시 정렬에 사용되는 배열을 전역변수로 선언해야 한다는 것이다.
• 기존의 데이터를 담을 추가적인 배열공간이 필요하다는 점에서 메모리 활용이 비효율적이라는 문제가 있다.

구현 소스

package org.kyh.algorithm;

public class mergeSort {

    static int number = 8;

    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; // sort배열 인덱스

        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++){
                sorted[k] = a[t];
                k++;
            }
        }else{
            for(int t=i; t <= middle; t++){
                sorted[k] = a[t];
                k++;
            }
        }

        //정렬된 배열을  삽입
        for(int t=m; t <= n; t++){
            a[t] = sorted[t];
        }
    }

    public static void mergeSort(int a[], int m, int n){

        if(m < n){
            int middle = (m+n)/2;
            mergeSort(a, m, middle);
            mergeSort(a,middle+1, n);
            merge(a, m, middle, n);

        }


    }

    public static void viewArray(int[] a){
        for(int i=0; i < a.length; i++){
            System.out.printf(a[i] + " ");
        }
    }


    public static void main(String[] args) {
       int[] array = {7,6,5,8,3,5,9,1};
        System.out.println(array.length);

        mergeSort(array, 0, array.length-1);

        viewArray(array);
    }
}

 

 

구현(수정)

package com.hyosung.sort;

public class MergeSort02 {

    static int[] buff;

    static  void __mergeSort(int[] a, int left, int right) {
        if(left < right) {
            int i;
            int center = (left+right)/2;

            int p =0;
            int j =0;
            int k =left;

            __mergeSort(a, left, center);
            __mergeSort(a, center+1, right);

            for(i = left; i <= center; i++) {
                buff[p++] = a[i];
            }

            while(i <= right && j < p){
                a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
            }

            while(j < p){
                a[k++] = buff[j++];
            }
        }
    }

    static void mergeSort(int[] a, int n) {
        buff = new int[n];

        __mergeSort(a, 0, n-1);

        buff = null;
    }

    public static void main(String[] args) {

        int[] x = {22,5,11,32,120,68,70};
        int nx = x.length;

        mergeSort(x, nx);

        System.out.println("=======");

        for(int i=0; i < x.length; i++){
            System.out.print(x[i] + " ");
        }
    }
}