07-6 병합 정렬

※ 병합정렬(Merge Sort)

 - 분할, 정복, 결합의 순서로 이루어 지는 정렬

 - 분할(divide) : 2개의 부분집합으로 분할

 - 정복(conquer) : 부분집합의 원소들을 정렬한다. 부분집합의 크기가 충분히 작지 않으면 다시 분할한다.

 - 결합(combine) : 정렬된 부분집합들을 하나의 집합으로 통합한다.

 - 새로 병합하여 만든 부분집합을 저장할 공간이 추가로 필요하기 때문에 정렬할 원소 n개에 대하여 

   2*n개의 메모리 공간을 사용한다.

※ 분할

※ 병합

※정렬과정

※ 구현

MergeSort

public class MergeSort {

       

       int[] result =null;

       int[] a=null;

       

       public void sorting(int[] a, int start, int end){

              if(this.a == null){

                     this.a= a;

                     result = new int[a.length];

              }

              if(end>start){

                     int middle = (end+start)/2;

                     sorting(this.a, start, middle);

                     sorting(this.a, middle+1 , end);

                     merge(start,middle,end);

              }

       }

       

       public void merge(int start, int middle, int end){

              

              int lStart = start;

              int rStart = middle+1;

              int resultIdx = start;

              

              while(lStart <= middle && rStart <= end){

                     if(a[lStart]>a[rStart]){

                           result[resultIdx] = a[rStart];

                           rStart++;

                           resultIdx++;

                     }else{

                           result[resultIdx] = a[lStart];

                           lStart++;

                           resultIdx++;

                     }

              }

              

              if(lStart <= middle){

                     for(int i=lStart; i<=middle; i++, resultIdx++){

                           result[resultIdx] =a[i];                           

                     }

              }else{

                     for(int i=rStart; i<=end; i++, resultIdx++){

                           result[resultIdx] =a[i];

                     }

              }

              

              for(int i =0; i<=end ; i++){

                     a[i] = result[i];

              }

              

              printMergeSort();

       }

       

       public void printMergeSort(){

              System.out.print("\n정렬된 원소 : ");

              for(int i=0; i <result.length; i++){

                     System.out.print(result[i]+" ");

              }

              System.out.println();

       }

}

Main

public class Main {

       public static void main(String[] args) {

              int a[] = {69,10,30,2,16,8,31,22};

              int size = a.length;

              MergeSort ms = new MergeSort();

              System.out.print("\n정렬할 원소 : ");

              for(int i =0; i<a.length; i++){

                     System.out.print(a[i]+" ");

              }

              

              ms.sorting(a, 0, size-1);

              System.out.println();

       }

}