[알고리즘] 🤪 이죵과 병합정렬(Merge Sort)에 대해서 알아보자

오랜만에 작성하는 알고리즘 포스팅:)

오늘은 정렬중에 병합정렬 즉, 머지소트를 작성해보고자 한다.

때때로 알고리즘 시험중에 외부 라이브러리를 사용할 수 없어 직접 구현해야하는 경우가 있다.

그러니 이번기회에 개념을 정리하며 나와같이 머리에 넣어보도록 하자! 😚

🧁 병합 정렬(merge sort) 알고리즘?

• 존 폰 노이만(John von Neumann)이라는 사람이 제안한 방법
• 병합 정렬은 분할정복 방식과 재귀 알고리즘을 이용한 정렬알고리즘이다.
• 즉, 주어진 배열을 원소가 하나밖에 남지 않을 떄까지 계속 둘로 쪼갠 후에 다시 크기순으로 재배열 하면서 원래 크기의 배열로 합치는걸 반복한다.
• 병합정렬의 구조상 최대한 작게 문제를 쪼개어 앞의 부분 리스트부터 차례대로 합쳐나가기 때문에 안정정렬 알고리즘이기도 하다. 😀

🧁 병합 정렬(merge sort) 예시

[3, 2, 6, 7, 1, 8, 4, 5]

먼저 가운데를 기준으로 배열을 쪼갭니다.

[3, 2, 6, 7] [1, 8, 4, 5]

그리고 이걸 최소까지 쪼개봅시당.

[6, 5] [3, 1] [8, 7] [2, 4]

[6] [5] [3] [1] [8] [7] [2] [4]

더이상 쪼갤수가 없다면? 두개씩 다시 합쳐는데 합칠때는 작은 숫자가 앞에 큰 숫자가 뒤에 위치시키게 변경해 봅시다.

[5, 6] [1, 3] [7, 8] [2, 4]

그 이후에 2개를 또 4개로 합쳐봅시다! 똑같이 작은 숫자가 앞에 큰 숫자가 뒤에 위치시키게 변경합니다.

[1, 3, 5, 6] [2, 4, 7, 8]

최종적으로 남은 2개의 데이터들을 비교해가며 하나로 합치면 정렬된 배열을 얻을 수 있답니다!

[1, 2, 3, 4, 5, 6, 7, 8]

🧁 병합 정렬(merge sort) 특징

• 병합정렬은 분할과 병합 단계로 나뉘고, 단순히 나뉘는 분할비용보다 모든 값들을 비교하는 병합 비용이 더 높습니다!
• 8 → 4 → 2 → 1 로 반복되는 수가 점점 절반으로 줄어들 기 때문에 O(logN)의 시간이 필요하고, 병합시에는 모든 값을 비교해야하므로 O(N)의 시간이 소모됩니다.
  • 즉, 총 시간복잡도는 O(NlogN)입니다!
• 두 개의 배열을 병합시 병합 결과를 담아놓을 배열이 추가로 필요하므로 공간복잡도는 O(N)입니다.

🧁 병합 정렬(merge sort) 구현

그럼 코드로 한번 살펴볼까용?

재귀를 이용해서 배열을 더 이상 나눌수 없을 때 까지 쪼갠 후 합쳐봅시당

Java

package Sort;

public class MergeSort {

    public static int[] sorted;
    public static StringBuilder sb;
    public static int N;      // 합치는 과정에서 정렬하여 원소를 담을 임시배열

    public static void merge_sort(int[] arr) {

        sorted = new int[arr.length];
        merge_sort(arr, 0, arr.length - 1);
        sorted = null;
    }

    // Top-Down 방식 구현
    private static void merge_sort(int[] arr, int left, int right) {

        // 더이상 쪼갤수 없는경우 return
        if (left == right) return;

        // 중간점
        int mid = (left + right) / 2;

        merge_sort(arr, left, mid);        // 왼쪽 부분배열(left ~ mid)
        merge_sort(arr, mid + 1, right);    // 오른쪽 부분배열(mid+1 ~ right)

        merge(arr, left, mid, right);        // 병합

    }

    /**
     * 병합구역 = arr배열의 left ~ right
     *
     * @param arr   정렬할 배열
     * @param left  배열의 시작점
     * @param mid   배열의 중간점
     * @param right 배열의 끝 점
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        int l = left;        // 왼쪽 부분배열 시작점
        int r = mid + 1;    // 오른쪽 부분배열 시작점
        int idx = left;        // 채워넣을 배열의 인덱스

        while (l <= mid && r <= right) {

            // 왼쪽배열 l번째가 오른쪽배열 r번째보다 작거나 같은경우 왼쪽 l을 새배열에 넣고 l과 idx 1증가
            if (arr[l] <= arr[r]) {
                sorted[idx] = arr[l];
                idx++;
                l++;
            }
            // 오른쪽배열 r번째가 왼쪽배열 l번째보다 작거나 같은경우 오른쪽 r번째를 새배열에 넣고 r과 idx 1증가
            else {
                sorted[idx] = arr[r];
                idx++;
                r++;
            }
        }

        if (l > mid) { // 왼쪽배열 모두 새배열에 다 들어갔다면
            while (r <= right) { // 오른쪽 배열이 남아있다면
                sorted[idx] = arr[r]; // 오른쪽 부분배열에 나머지를 새 배열에 넣기
                idx++;
                r++;
            }
        } else { // 오른쪽 배열이 모두 새 배열에 들어갔다면
            while (l <= mid) { // 왼쪽 배열이 아직 남아있다면
                sorted[idx] = arr[l]; // 왼쪽 배열의 나머지를 새 배열에 넣기
                idx++;
                l++;
            }
        }

        sb.append("#").append(N++).append("\n");
        for (int i = left; i <= right; i++) { //정렬된 새 배열을 기존의 배열에 복사
            arr[i] = sorted[i];
            sb.append(arr[i]).append(" ");
        }
        sb.append("\n");
    }

    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 6, 7, 1, 8, 4, 5};
        sb = new StringBuilder();
        N = 0;
        merge_sort(arr);

        sb.append("#In arr").append("\n");
        for (int i = 0; i < arr.length; i++) { //정렬된 새 배열을 기존의 배열에 복사
            sb.append(arr[i]).append(" ");
        }
        sb.append("\n");

        System.out.println(sb);

    }

}

해당 개념을 잘 익혀서 알고리즘 시험때 써먹어봅시다! :)