Sorting Algorithms - 합병 정렬(Merge Sort)

Park Suyong·2020년 9월 16일
0

개인 알고리즘

목록 보기
5/19

1. 정의

합병 정렬(Merge Sort)분할 정복(Divide and Conquer) 방식으로 배열을 분할하고, 최종적으로 분할된 배열에서 대소 비교를 이룬 뒤 다시 배열을 합치는 정렬 방식이다.

2. 방식

배열을 중간 인덱스를 기준으로 좌, 우로 나눈다. 이 방식을 지속적으로 반복하며 최종적으로 Partition에 2개의 요소가 남을 때까지 반복한다. 아래 그림을 참고하자.

위의 그림에서 가운데 부분을 보자. 가운데 부분에서는 바로 윗 단계의 2개의 요소로 구성된 Partition 에서 대소 비교를 진행하고, 그 다음부터 합병을 진행하게 되는 것이다.
따라서, 지속적으로 배열을 분할하다가 특정 지점에서 대소 비교를 이루고 배열을 합병하면 되는 것이다. 바로 코드를 보도록 한다.

3. 구현

public static void main(String[] args) {
        System.out.println("병합/합병 정렬을 실시합니다.");
        int[] arr = {78, 33, 95, 18, 45, 91, 58, 23, 75, 69, 78, 52, 38, 98, 68, 90, 36, 19};
        int[] temp = new int[arr.length];

        MergeSort(arr, temp, 0, arr.length - 1);
        for(int i : arr) System.out.print(i + " ");
    }

    public static void MergeSort(int[] arr, int[] temp, int low, int high) {

        if(low < high) {
            int mid = (high + low) / 2;
            MergeSort(arr, temp, low, mid);
            MergeSort(arr, temp, mid + 1, high);
            // 위 2개의 재귀함수 호출로 인해 배열의 부분이 지속적으로 분할된다.
            // 배열의 분열을 마쳤으므로 정렬을 시작하도록 한다.
            Merge(arr, temp, low, mid, high);
        }
    }

    public static void Merge(int[] arr, int[] temp, int low, int mid, int high) {

        for(int i = low; i <= high; i++) // 임시 배열에 원래 배열을 필요한 만큼 복사해 준다.
            temp[i] = arr[i];

        int part1 = low;        // 좌측 배열의 첫 번째 인덱스
        int part2 = mid + 1;    // 우측 배열의 첫 번째 인덱스
        int index = low;        // 양쪽 배열에서 작은 값을 복사할 때마다 결과 배열에 어디에 저장할지 나타내는 변수
        while(part1 <= mid && part2 <= high) { // 양쪽 배열을 끝까지 돌도록 한다.
            if(temp[part1] < temp[part2]) { // 앞의 배열의 원소가 작은 경우
                arr[index] = temp[part1];
                part1++;
            }
            else {  // 뒤의 배열의 원소가 작은 경우
                arr[index] = temp[part2];
                part2++;
            }
            index++;
        }

        // 만약, 주어진 배열이 홀수개이거나 한 경우 좌측 배열에서 하나는 끝났는데 다른 하나는 끝나지 않았을 것이다.
        // 띠리서, 배열에 값을 다 넣어주기 위해서 아래의 코드를 실행한다.
        // 참고로 위 while 반복문이 끝나면 최종 인덱스는 index 이다.
        for(int i = 0; i <= mid - part1; i++)
            arr[index + i] = temp[part1 + i];
    }
병합/합병 정렬을 실시합니다.
18 19 23 33 36 38 45 52 58 68 69 75 78 78 90 91 95 98 

구현 코드 및 실행 결과는 위 그림과 같다.

이러한 합병 정렬은 시간 복잡도를 항상 O(nlogn)으로 갖게 된다.

profile
Android Developer

0개의 댓글