ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Sort] 합병 정렬(Merge Sort)
    CSE/Sort 2015. 6. 12. 15:46

    합병 정렬(Merge Sort)


     

     


    [출처: 위키]



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



    Divide & Conquer !!!!





    1단계





     



    자 위와 같이 숫자를 두고 정렬을 해봅시다!!





    합병 정렬의 개념은 일단 다시 그림을 그려서 설명해야 겠네요~




     


    이렇게 처음에는 붙어있다고 생각하세요!!


    여기서 1개의 원소집합을 갖는 부분 집합으로 쪼갭니다~




    처음엔 요렇게 2등분 했다고 보죠



     





    다음은 분리된 걸 또 분리.





     



    또! 분리...



     


    각각 1개의 원소로 분리 됬네요~?


    네 여기까지 분할 단계를 끝마치네요~!












    2단계



    이젠 다시 합쳐야 할 시간입니다!!!


    합치면서 정렬됩니다!!


    자 위 그림에서 등분된 집합이 다시 합쳐지는 꼴을 봅시다!!




     


    이렇게 4개의 부분 집합으로 다시 합쳐졌죠???


    근데 합치면서 달라지신게 보일겁니다!!!


    각 부분 집합이 정렬이 되었죠??



    네. 여기가 포인트 입니다!


    합쳐지면서 정렬이 이루어 집니다!





    그럼 또 합쳐 봅시다!



     



    자 이렇게 되었네요!!


    마지막 단계만 남겨둔 상태군요...




     


    이렇게 정렬이 완성이군요!!



    여기서는 2-way 병합 정렬을 수행했습니다!!


    2개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 방식이거든요!!!


    이처럼 n-way로 작성을 따로 할 수도 있습니다!!!







     


    이 병합 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!


    모든 케이스에 대해


     



     


    를 갖습니다!!!




    자 그럼 소스 코드로 예제를 살펴 봅시다~



    MergeMain.java


     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    package Merge;
     
    public class MergeMain {
        public static void main(String[] args) {
            int[] arr = { 69103021683122 };
            MergeSort.mergeSort(arr, 0, arr.length - 1);
        }
    }
     
     
    cs



    MergeSort.java

     

    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
    47
    48
    49
    50
     
    package Merge;
     
    import Selection.SelectionSort;
     
    public class MergeSort {
        public static int[] sorted = new int[30];
     
        public static void mergeSort(int[] arr, int m, int n) {
            int middle;
            if (m < n) {
                middle = (m + n) / 2;
                mergeSort(arr, m, middle);
                mergeSort(arr, middle + 1, n);
                merge(arr, m, middle, n);
            }
        }
     
        public static void merge(int[] arr, int m, int middle, int n) {
            int i, j, k, t;
     
            i = m;
            j = middle + 1;
            k = m;
     
            while (i <= middle && j <= n) {
                if (arr[i] <= arr[j])
                    sorted[k] = arr[i++];
                else
                    sorted[k] = arr[j++];
                k++;
            }
     
            if (i > middle) {
                for (t = j; t <= n; t++, k++)
                    sorted[k] = arr[t];
            } else {
                for (t = i; t <= middle; t++, k++)
                    sorted[k] = arr[t];
            }
     
            for (t = m; t <= n; t++)
                arr[t] = sorted[t];
     
            System.out.println("\n 합병 정렬 >> ");
            SelectionSort.printArr(arr);
     
        }
    }
     
    cs




    결과는 아래와 같습니다!!


     



     



    'CSE > Sort' 카테고리의 다른 글

    [Sort] 힙 정렬(Heap Sort]  (2) 2015.06.12
    [Sort] 기수 정렬(Radix Sort)  (0) 2015.06.12
    [Sort] 셸 정렬(Shell Sort)  (0) 2015.06.12
    [Sort] 퀵 정렬(Quick sort)  (1) 2015.06.12
    [Sort] 삽입 정렬(Insertion sort)  (0) 2015.06.12
    [Sort] 버블 정렬(Bubble Sort)  (0) 2015.06.12

    댓글

Designed by Tistory.