고급정렬 - MergeSort (합병정렬)

정렬 과정

https://ko.wikipedia.org/wiki/합병_정렬

 

흔히 쓰이는 하향식 2-way 합병 정렬은 다음과 같이 작동한다.

리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.

 

이 과정에서 재귀 함수를 활용한다.

분할 후 분할된 2개의 조각에 다시 합병정렬을 실행한다.

 

분할과 정복.

 

구현 코드

package net.jetalab.excercise.mergesort;

import java.util.Scanner;

public class Main {
    public static int[] arr, tmp;

    public static void merging(int startIdx, int midIdx, int endIdx) {
        /* 파티션 기준 앞과 뒤를 병합 */

        int cur1 = startIdx, cur2 = midIdx + 1, cur3 = 0; // 커서 초기화

        tmp = new int[endIdx - startIdx + 1]; // 병합된 결과를 임시 저장할 배열

        while (cur1 <= midIdx && cur2 <= endIdx) { // 양쪽 배열 중 한 쪽을 모두 임시 배열에 저장할 때 까지 반복
            if (arr[cur1] <= arr[cur2]) {  // 더 작은 쪽을 임시 배열에 저장
                tmp[cur3++] = arr[cur1++];
            } else {
                tmp[cur3++] = arr[cur2++];
            }
        }

        if (cur1 <= midIdx) { // 앞쪽이 남았다면
            while (cur1 <= midIdx) tmp[cur3++] = arr[cur1++]; // 모두 밀어넣기
        } else { // 뒤쪽이 남았다면
            while (cur2 <= endIdx) tmp[cur3++] = arr[cur2++]; // 모두 밀어넣기
        }

        cur3 = startIdx;
        for (int e : tmp) arr[cur3++] = e; // 원본 배열로 옮기기
    }

    public static void mergeSort(int startIdx, int endIdx) {
        if (startIdx == endIdx) return; // 길이가 1이라면 본인을 반환

        int midIdx = (startIdx + endIdx) / 2; // 중간 index
        mergeSort(startIdx, midIdx); // 좌측 정렬
        mergeSort(midIdx + 1, endIdx); // 좌측 정렬
        merging(startIdx, midIdx, endIdx); // 좌측 우측을 병합
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        System.out.print("원소의 갯수를 입력해주세요: ");
        int size = Integer.parseInt(scan.nextLine());
        arr = new int[size];

        System.out.print("정렬할 원소를 입력해주세요: ");
        for (int i = 0; i < size; i++) {
            arr[i] = scan.nextInt();
        }

        mergeSort(0, size - 1); // 정렬 실행
        for (int e : arr) System.out.print(e + " "); // 정렬 결과 출력
    }
}

 

참고 문서

합병 정렬 - 위키백과, 우리 모두의 백과사전 - https://ko.wikipedia.org/wiki/합병_정렬