병합정렬

1. 병합정렬

병합정렬은 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘이다.

배열 a,와 b를 비교하여 작은 값을 꺼내 c에 넣는다.

2. 두 배열을 병합하는 배열병합 코드

package myTest4;
 
import java.util.Scanner;
 
public class MergeArray {
    
    // 배열 요소 a[idx1]과 a[idx2]의 값을 바꿉니다.
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1]; 
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    // 정렬을 마친 배열 a,b를 병합하여 배열 c에 저장합니다.
    static void merge(int[] a, int na, int[] b, int nb, int[] c){
        int pa = 0;
        int pb = 0;
        int pc = 0;
        
        while(pa < na && pb < nb){        // 작은 값을 저장합니다.
            c[pc++] = (a[pa] <= b[pb]) ? a[pa++] : b[pb++];
        }
        while(pa < na){            // a에 남아있는 요소를 복사합니다.
            c[pc++] = a[pa++];
        }
        
        while(pb < nb){
            c[pc++] = b[pb++];
        }
    }
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int[] a = {2,4,6,8,11,13};
        int[] b = {1,2,3,4,9,16,21};
        int[] c = new int[13];
        
        System.out.println("두 배열의 병합");
        merge(a, a.length, b, b.length, c);        // 배열 a와 b를 병합하여 c에 저장
        System.out.println("배열 a와 b를 병합하여 배열 c에 저장했습니다.");
        System.out.println("배열 a:");
        for(int i=0; i< a.length; i++){
            System.out.println("a["+i+"]=" + a[i]);
        }
        System.out.println("배열 b:");
        for(int i=0; i< b.length; i++){
            System.out.println("b["+i+"]=" + b[i]);
        }
        System.out.println("배열 c:");
        for(int i=0; i< c.length; i++){
            System.out.println("c["+i+"]=" + c[i]);
        }
    }
}

결과

두 배열의 병합
배열 a와 b를 병합하여 배열 c에 저장했습니다.
 
배열 a:
a[0]=2
a[1]=4
a[2]=6
a[3]=8
a[4]=11
a[5]=13
 
배열 b:
b[0]=1
b[1]=2
b[2]=3
b[3]=4
b[4]=9
b[5]=16
b[6]=21
 
배열 c:
c[0]=1
c[1]=2
c[2]=2
c[3]=3
c[4]=4
c[5]=4
c[6]=6
c[7]=8
c[8]=9
c[9]=11
c[10]=13
c[11]=16
c[12]=21

정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬(merge sort)라고 한다.

먼저 배열을 앞부분과 뒷부분으로 나눈다.  배열의 요소 갯수가 12개 이므로 6개의 배열로 각각 나눈다.

두 배열을 각각 정렬하고 병합하면 배열 모두를 정렬 할 수 있다.

3. 병합정렬 소스코드

package myTest4;
 
import java.util.Scanner;
 
public class MergeSort {
    
    static int[] buff;        // 작업용 배열
    
    // a[left] ~ a[right] 를 재귀적으로 병합 정렬
    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){
        Scanner stdIn = new Scanner(System.in);
        
        System.out.println("병합 정렬");
        System.out.print("배열의 길이 : ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];
        for(int i=0; i< nx; i++){
            System.out.print("x[" + i + "] : ");
            x[i] = stdIn.nextInt();
        }
        
        mergeSort(x,nx);        // 배열 x를 병합 정렬합니다.
        System.out.println("오름차순으로 정렬했습니다.");
        for(int i=0; i<nx; i++){
            System.out.println("X[" + i + "]= " + x[i]);
        }
    }    
}
 

결과

병합 정렬
배열의 길이 : 10
x[0] : 10
x[1] : 9
x[2] : 8
x[3] : 7
x[4] : 6
x[5] : 5
x[6] : 4
x[7] : 3
x[8] : 2
x[9] : 1
오름차순으로 정렬했습니다.
X[0]= 1
X[1]= 2
X[2]= 3
X[3]= 4
X[4]= 5
X[5]= 6
X[6]= 7
X[7]= 8
X[8]= 9
X[9]= 10