[정렬] 합병정렬 (Merge Sort)

* 합병정렬 (Merge Sort)

"여러 개의 정렬된 자료의 집합을 결합하여 한개의 정렬된 집합으로 만드는 방법 "

Divide and Conquer (분할 정복) + Combine (결합) : 재귀적 구현 필요

전체 원소들에 대해서 정렬을 수행하지 않고 부분집합으로 분할(divide)하고

각 부분집합에 대해서 정렬을 완성(conquer)한 후에 정렬된 부분집합들을 다시 결합(combine)

시간복잡도 : O(nlog(n)) 

최악의 경우에도 nlogn을 보장한다. (비교)*(횟수)

※ 오름차순 정렬에 대한 설명.

input = [27, 2, 46, 4, 19, 50]

합병정렬은 말 그대로 나누고, 정렬하고, 합치는 과정을 반복하는 정렬 방법이다.

큰 문제를 작은문제로 나누어서 작은 문제부터 해결하면서 점점 큰 문제를 해결해 나간다.

아래 그림을 보면 전체 요소 중 일부만을 떼어내어 정렬을 수행한다.

전체 요소를 반으로 나누고 또 나누는 작업을 반복해서 두개의 값을 비교하는 것 부터 시작한다.

 

정렬 된 2, 7을 다시 원래 위치로 옮겨준다.

다시 전체의 부분 요소인 (2, 27), 46 에 대해 정렬을 수행한다. 

정렬이 완료되었으니 다시 원래의 위치로 이동시켜 준다.

전체 요소의 왼쪽 요소들에 대해 정렬을 완료했기 때문에

오른쪽 요소들에 대해 정렬을 시작한다.

오른쪽 요소들을 나누고 나눠 가장 작은 두개의 요소를 비교하는 것 부터 다시 시작한다.

두개 요소에 대해 정렬이 수행되고나면 원래 위치로 이동시켜 준다.

다시 전체의 부분 요소인 (4, 19), 50 을 정렬 시킨다.

정렬이 완료되면 다시 원래의 위치로 올려주고

정렬된 왼쪽요소(2, 27, 46) 그리고 오른쪽요소(4, 19, 50)을 비교한다.

전체 요소에 대한 비교가 이렇게 완료되었다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

MergeSort.java  public class MergeSort {     private static int[] sort = new int[30];       public static void mergeSort(int left, int right,int[] arr){         int mid;         if(left<right){             mid = (left+right)/2;             mergeSort(left, mid, arr);             mergeSort(mid+1, right, arr);             merge(left, mid, right, arr);         }     }       public static void merge(int left, int mid, int right, int[] arr){         int l = left;         int m = mid+1;         int k = left;           while(l<=mid || m<=right){             if(l<=mid && m<=right){                 if(arr[l]<=arr[m]){                     sort[k] = arr[l++];                 }else{                     sort[k] = arr[m++];                 }             }else if(l<=mid && m>right){                 sort[k] = arr[l++];             }else{                 sort[k] = arr[m++];             }                          k++;         }                  for(int i=left; i<right+1; i++){             arr[i] = sort[i];         }                  System.out.print("합병정렬 = ");         for(int i=0; i<arr.length; i++){             System.out.print(arr[i] + " ");         }           System.out.println();                                                               } }

                                          

1 2 3 4 5 6 7 8

test.java  public class test {     public static void main(String[] args) {                               int[] arr = new int[]{27, 2, 46, 4, 19, 50};         int left = 0, right = arr.length-1;                  MergeSort.mergeSort(left, right, arr);        } }

test.java 를 실행하면 아래와 같은 결과가 수행된다.

   

참고 사이트 : http://visualgo.net/

* 사이트를 통해 자세한 알고리즘 작동 방법을 확인할 수 있습니다.