[Algorithm Week_3] MergeSort

MergeSort

Stable Sort

---

Recursion으로 생각?

1. 배열을 2등분

2. 2등분 한 각 subarray들을 정렬 "By Recursion"

3. 정렬된 2개의 subarray들을 "Merge"

 

최종 "Merge" 방식

i는 왼쪽 subarray 전용 포인터이고, j는 오른쪽 subarray 전용 포인터이다

- 여기서 i, j가 가리키는 각 값들을 비교해서 최종 정렬된 배열에 넣어준다

• 오름차순 배열이 default이므로, 더 작은 값을 넣어준다

 

1) i : 4 & j : 1

4 > 1 이므로, j가 가리키는 값인 1을 배열에 넣어주고 j는 증가시켜준다

 

 

2) i : 4 & j : 2

4 > 2 이므로, j가 가리키는 값인 2를 배열에 넣어주고 j는 증가시켜준다

 

3) i : 4 & j : 5

4 < 5 이므로, i가 가리키는 값인 4를 배열에 넣어주고 i는 증가시켜준다

 

 

4) i : 6 & j : 5

6 > 5 이므로, j가 가리키는 값인 5를 배열에 넣어주고 j는 증가시켜준다

 

 

5) i : 6 & j : 10

6 < 10 이므로, i가 가리키는 값인 6을 배열에 넣어주고 i는 증가시켜준다

 

6) i : 8 & j : 10

8 < 10 이므로, i가 가리키는 값인 8을 배열에 넣어주고 i는 증가시켜준다

 

7) i : 9 & j : 10

9 < 10 이므로, i가 가리키는 값이 9를 배열에 넣어주고 i는 증가시켜준다

 

 

8) i : out & j : 10

i는 왼쪽 subarray 전용 포인터이다. 그런데 i는 지금 해당 영역을 벗어났다. 이 의미는 왼쪽 subarray의 모든 요소들은 이미 최종 배열에 정렬이 완료되었다는 의미이고, 이제 포인터 j의 영역의 요소들을 전부 최종 배열에 넣어주면 된다

 

---

Java Code

static void MergeSort(int [] list, int left, int right){
    /*
    list는 우리가 코드를 작성할 때는 그냥 recursion으로 던져버리지만,
    상세히 보면 list는 결국 계속해서 쪼개지면서 최종적으로는 길이가 1인 list가 된다
    */

    if(left < right){
        int mid = (left + right) / 2;
        MergeSort(list, left, mid);
        MergeSort(list, mid + 1, right);
        Merge(list, left, mid, right);
    }
}

static void Merge(int [] list, int left, int mid, int right){
    int i = left;
    int j = mid + 1;
    /*
    1. Recursion적으로 생각해보면 우리는 결국 하나의 Array를 2개의 subarray로 나누었고
    2. 2개의 subarray를 각각 정렬 후 (By Recursion)
    3. 정렬된 2개의 subarray를 이 메소드에서 최종적으로 "Merge"한다
    >> 따라서, "int i"는 왼쪽 subarray의 영역을 담당하고, "int j"는 오른쪽 subarray의 영역을 담당하도록 설정
    >> "int i & int j"는 본인이 담당하는 영역을 벗어나면 안된다
     */

    for(int k=left; k<=right; k++){
        if(j > right){
            /*
            "int j"는 오른쪽 subarray를 담당하고, 오른쪽 subarray의 마지막 index는 "int right"이다
            조건식에서 "j > right"는 "int j"는 본인이 담당하는 영역을 벗어낫다는 의미이다
            >> 따라서 오른쪽 subarray는 모두 '배열 MergeSortedArray'로 옮겨진 상태이고
                이 상태에서는 "int i"가 담당하는 영역의 요소들만 '배열 MergeSortedArray'로 옮겨주면 된다
             */
            MergeSortedArray[k] = list[i++];
        }
        else if(i > mid){
            /*
            "int i"는 왼쪽쪽 subarray를 담당하고, 왼쪽 subarray의 마지막 index는 "mid"이다
            조건식에서 "i > mid"는 "int i"는 본인이 담당하는 영역을 벗어낫다는 의미이다
            >> 따라서 왼쪽 subarray는 모두 '배열 MergeSortedArray'로 옮겨진 상태이고
                이 상태에서는 "int j"가 담당하는 영역의 요소들만 '배열 MergeSortedArray'로 옮겨주면 된다
             */
            MergeSortedArray[k] = list[j++];
        }
        else if(list[i] < list[j]){
            /*
            이 조건식에 도달했다는 의미는 "int i & int j"가 현재 본인들의 영역에서 벗어나지 않았다는 의미이다
            그러면 "MergeSort"를 기본적으로 ASC 배열을 만들려고 하기 때문에 작은 값을 MergeSortedArray로 옮기면 된다
             */
            MergeSortedArray[k] = list[i++];
        }
        else{
            MergeSortedArray[k] = list[j++];
        }
    }
}

 

시간복잡도 분석

- Recursion의 시간복잡도는 일단 점화식을 구해서 점화식을 이용해서 최종적인 시간복잡도를 구해야 한다

static void Merge(int [] list, int left, int mid, int right){
    int i = left;
    int j = mid + 1;

    for(int k=left; k<=right; k++){
        if(j > right){
            MergeSortedArray[k] = list[i++];
        }
        else if(i > mid){
            MergeSortedArray[k] = list[j++];
        }
        else if(list[i] < list[j]){
            MergeSortedArray[k] = list[i++];
        }
        else{
            MergeSortedArray[k] = list[j++];
        }
    }
}

일단 Merge함수의 시간복잡도는 O(n)이다

 

static void MergeSort(int [] list, int left, int right){
    if(left < right){
        int mid = (left + right) / 2;
        MergeSort(list, left, mid);
        MergeSort(list, mid + 1, right);
        Merge(list, left, mid, right);
    }
}

MergeSort(int [] list, int left, int right)의 연산 수행 횟수를 T(n)이라고 하면 (n은 list의 길이)

이 점화식을 풀면 최종적으로 MergeSort의 시간복잡도는 O(n log n)으로 표현된다

 

 

 

MergeSort는 언제나 시간복잡도가 O(n log n)으로 표현이 된다 (최악 / 평균 / 최선)

 

---

Full Code (Java)

package Week_3;

public class Merge_Sort {

    static int [] MergeSortedArray;

    public static void main(String[] args) {
        int [] list = {4, 6, 8, 9, 1, 2, 5, 10};
        MergeSortedArray = new int[list.length];

        System.out.println("정렬 전 list []");
        for(int n : list){
            System.out.print(n + " ");
        }

        MergeSort(list, 0, list.length - 1);

        System.out.println("\n\n정렬 후 list []");
        for(int n : MergeSortedArray){
            System.out.print(n + " ");
        }
    }

    static void MergeSort(int [] list, int left, int right){
        /*
        list는 우리가 코드를 작성할 때는 그냥 recursion으로 던져버리지만,
        상세히 보면 list는 결국 계속해서 쪼개지면서 최종적으로는 길이가 1인 list가 된다
        */

        if(left < right){
            int mid = (left + right) / 2;
            MergeSort(list, left, mid);
            MergeSort(list, mid + 1, right);
            Merge(list, left, mid, right);
        }
    }

    static void Merge(int [] list, int left, int mid, int right){
        int i = left;
        int j = mid + 1;
        /*
        1. Recursion적으로 생각해보면 우리는 결국 하나의 Array를 2개의 subarray로 나누었고
        2. 2개의 subarray를 각각 정렬 후 (By Recursion)
        3. 정렬된 2개의 subarray를 이 메소드에서 최종적으로 "Merge"한다
        >> 따라서, "int i"는 왼쪽 subarray의 영역을 담당하고, "int j"는 오른쪽 subarray의 영역을 담당하도록 설정
        >> "int i & int j"는 본인이 담당하는 영역을 벗어나면 안된다
         */

        for(int k=left; k<=right; k++){
            if(j > right){
                /*
                "int j"는 오른쪽 subarray를 담당하고, 오른쪽 subarray의 마지막 index는 "int right"이다
                조건식에서 "j > right"는 "int j"는 본인이 담당하는 영역을 벗어낫다는 의미이다
                >> 따라서 오른쪽 subarray는 모두 '배열 MergeSortedArray'로 옮겨진 상태이고
                    이 상태에서는 "int i"가 담당하는 영역의 요소들만 '배열 MergeSortedArray'로 옮겨주면 된다
                 */
                MergeSortedArray[k] = list[i++];
            }
            else if(i > mid){
                /*
                "int i"는 왼쪽쪽 subarray를 담당하고, 왼쪽 subarray의 마지막 index는 "mid"이다
                조건식에서 "i > mid"는 "int i"는 본인이 담당하는 영역을 벗어낫다는 의미이다
                >> 따라서 왼쪽 subarray는 모두 '배열 MergeSortedArray'로 옮겨진 상태이고
                    이 상태에서는 "int j"가 담당하는 영역의 요소들만 '배열 MergeSortedArray'로 옮겨주면 된다
                 */
                MergeSortedArray[k] = list[j++];
            }
            else if(list[i] < list[j]){
                /*
                이 조건식에 도달했다는 의미는 "int i & int j"가 현재 본인들의 영역에서 벗어나지 않았다는 의미이다
                그러면 "MergeSort"를 기본적으로 ASC 배열을 만들려고 하기 때문에 작은 값을 MergeSortedArray로 옮기면 된다
                 */
                MergeSortedArray[k] = list[i++];
            }
            else{
                MergeSortedArray[k] = list[j++];
            }
        }
    }
}