[ 알고리즘 ] 병합 정렬 - JAVA

백준 24060번 문제를 풀기 전에 병합 정렬 알고리즘의 로직에 대해
아주 자세히 포스팅 해보려 한다.
사실 이미지로 본다면 아주 쉬운데 이걸 구현하고자 하면 머리가 아플 수도 있다. 
때문에 이해하기 언제보더라도 이해하기 쉽게,
이번 포스팅은 한줄 한줄 뜯어보도록 하겠다.

합병 정렬 ( Merge Sort )

합병 정렬 or 병합 정렬이라고 하며, 비교 기반이고, 분할 정복 알고리즘 중 하나이다.

 존 폰 노이만이 1945년에 개발했다.

 

최악, 평균, 최선에서 일정한 시간 복잡도 O(n log n)를 가지며,

이는 배열을 나누는데 O(log n)

합병하는데 O(n)이 걸리기 때문이다.

 

순서는 다음과 같다.

 

1. 분할

정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분으로 나눈다.

 

2. 정복

각 부분 리스트를 재귀과정으로 정렬한다.

 

3. 결합

두 부분을 하나의 정렬된 리스트로 합병한다.

 

4. 복사

임시 배열에 저장된 결과를 원래 배열에 복사

 

---

 

다음과 같은 예시로 알아보자

8개의 정수를 가진 배열 Array가 존재한다.

int[] arr = {38, 27,33, 1, 43, 3, 9, 10};

 

다음을 그림과 같이 표현할 수 있다.

 

사실 이 그림은 합병 정렬이라면 지겹게 보았을 거다.

근데 이 그림만 보고서는 재귀적 요소 때문에 코드가 잘 이해되지 않을 수 있다.

 

분할

private static void mergeSort(int[] arr, int left, int right) {
    if(left < right) {
        int mid = (left + right) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

 

결합

private static void merge(int[] arr, int left, int mid, int right) {

    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1;
    int k = 0;

    while(i <= mid && j <= right) {
        if(arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];
        }
    }

    while(i <= mid) {
        temp[k++] = arr[i++];
    }

    while(j <= right) {
        temp[k++] = arr[j++];
    }


    for (int l = 0; l < temp.length; l++) {
        arr[left + l] = temp[l];
    }


}

 

MergeSort 메서드 - 1 [ mergeSort(arr, 0, 7) ]

•  다음과 같이 분할되어 재귀호출 한다.

MergeSort 메서드 - 2 [ mergeSort(arr, 0, 3) ]

•  다음과 같이 분할되어 재귀호출 한다.

 

MergeSort 메서드 - 3 [ mergeSort(arr, 0, 1) ]

• 이번에는 left == mid 와 mid + 1 == right 이기  때문에 if문에서 막혀 실행되지 않는다.
• 바로 다음 merge() 메서드가 실행된다.

Merge 메서드 - 4 [ merge(arr, 0, 0, 1) ]

• 먼저 병합할 개수만큼 temp 배열을 생성한다.
• 이후 다음 코드와 같이 각각 시작할 값을 설정한다
  • 왼쪽 분할 리스트에서 시작값 --> left ex) 0
  • 오른쪽 분할 리스트에서 시작값 -> mid + 1 ex) 1

• 이후 다음 첫 번째 코드로 인해 temp에 위 그림과 같이 저장된다.
• 그 다음 두 번째 코드로 기존 배열에 정렬된 값이 저장된다.
  • 기존의 값들 만큼만 꺼내고 그 값들로만 정렬하여 다시 재배치 하기 때문에 그대로 넣어주기만 하면 된다.

while(i <= mid && j <= right) {
    if(arr[i] <= arr[j]) {
        temp[k++] = arr[i++];
    }
    else {
        temp[k++] = arr[j++];
    }
}

for (int l = 0; l < temp.length; l++) {
    arr[left + l] = temp[l];
}

MergeSort 메서드 - 5 [ mergeSort(arr, 2, 3) ] & Merge 메서드 - 6 [ merge(arr, 2, 2, 3) ]

• 2번 째 스텝의 분할된 오른쪽 리스트를 처리할 차례이다.
• 4번 째와 동일한 방법으로 실행된다. ( 간략하게 코드는 제외 후 그림만 )

Merge 메서드 - 7 [ merge(arr, 0, 1, 3) ]

•  2번 째 스텝에서 재귀 호출을 모두 마치고 이 코드로 돌아왔다.
• 그렇다면 이제 합병 정렬할 차례이다.

• 먼저 초기 값들은 다음과 같이 구성된다.

• 이후 다음과 같은 코드를 통해 진행된다.

while(i <= mid && j <= right) {
    if(arr[i] <= arr[j]) {
        temp[k++] = arr[i++];
    }
    else {
        temp[k++] = arr[j++];
    }
}

 

1회전 - arr[i] = 27 > arr[j] = 1

2회전 - arr[ i ] = 27 <= arr[ j ] = 33

3회전 - arr[ i ] = 38 > arr[ j ] = 33

• 이 이후는 j = 4로 right = 3 보다 크기 때문에 while문을 빠져나온다.
• 그렇다면 잔여값은 어떻게 될까

 

 

while(i <= mid) {
    temp[k++] = arr[i++];
}

while(j <= right) {
    temp[k++] = arr[j++];
}

 

• 위 코드를 통해 기존의while(i <= mid && j <= right) { 코드 형태를 유지한 채 i or j 중 최대에 도달하지 못했다면 남은 자리를 잔여 값으로 채워준다.
• 다음 잔여값을 넣어야 할 위치는? k가 가지고 있다.

• 이후 이전과 같이 temp값을 그대로 넣어준다.

for (int l = 0; l < temp.length; l++) {
    arr[left + l] = temp[l];
}

이후

이후에는 분할된 남은 부분 즉, MergeSort 메서드 - 1 [ mergeSort(arr, 0, 7) ] 부분에서 이루어진 오른쪽 리스트들을 분할 정복하면 된다. 이는 그림과 같이 한번 직접 해보시길 바란다.

 

정렬 전 : [38, 27, 33, 1, 43, 3, 9, 10]
정렬 후 : [1, 3, 9, 10, 27, 33, 38, 43]

 

 

합병 정렬은 임시 메모리를 생성해야 하기 때문에
큰 배열에서는 메모리 사용량이 크다. 하지만 안정적인 정렬로 고려해서 사용하는게 좋다.

이번 정렬은 간단하면서도 복잡한 알고리즘으로
기본적인 분할 정복 알고리즘의 대표적인 예라고 생각한다.
때문에 꼭 이 알고리즘을 정복하고 넘어가는 것을 추천한다.

전체 코드

import java.util.Arrays;

//TIP 코드를 <b>실행</b>하려면 <shortcut actionId="Run"/>을(를) 누르거나
// 에디터 여백에 있는 <icon src="AllIcons.Actions.Execute"/> 아이콘을 클릭하세요.
public class Main {

    private static void mergeSort(int[] arr, int left, int right) {
        if(left < right) {
            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {

        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1;
        int k = 0;

        while(i <= mid && j <= right) {
            if(arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            }
            else {
                temp[k++] = arr[j++];
            }
        }

        while(i <= mid) {
            temp[k++] = arr[i++];
        }

        while(j <= right) {
            temp[k++] = arr[j++];
        }


        for (int l = 0; l < temp.length; l++) {
            arr[left + l] = temp[l];
        }


    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 33, 1, 43, 3, 9, 10};
        System.out.println("정렬 전 : " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length - 1);

        System.out.println("정렬 후 : " + Arrays.toString(arr));
    }
}