자료구조 - 정렬 3 (Merge)

 

전체 정렬 개요의 설명은 여기를 참조
Bubble / Selection / Insertion 정렬의 설명은 여기를 참조
Shell 정렬의 설명은 여기를 참조
Quick 정렬의 설명은 여기를 참조
Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조
Counting 정렬의 설명은 여기를 참조
Radix 정렬의 설명은 여기를 참조
Bucket 정렬의 설명은 여기를 참조
Topological 정렬의 설명은 여기를 참조

 

Merge Sort(병합 정렬)

 

애니메이션만 봐도 굉장히 쉽게 이해할 수 있다. 아래를 확인하자.

 

병합 정렬. 출처 : https://velog.io/@emily0_0/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Merge-Sort

 

병합 정렬은 존 폰 노이만(John von Neunmann)이 제안한 Stable 정렬의 기법이다. 위의 애니메이션만 봐도 쉽게 이해가 가능한데, 말 그대로 기존의 배열을 반으로 지속적으로 나누어 1개만 남을 때까지 분할한 다음 다시 정렬해가며 하나로 합치는 방식이다.

분할 후 병합의 과정을 거치기에 이는 분할 정복 알고리즘(Divide and Conquer Algorithm)의 하나에 속한다.

 

※ 분할 정복 알고리즘이란?

하나의 큰 문제를 작은 문제로 분리한 뒤 각각을 해결하여, 결과를 모아 원래 문제를 해결하는 방법.
대개 재귀 호출을 이용하여 구현된다.

 

병합 정렬의 특징은 다음과 같다.

특성	설명
Not In-place 알고리즘	배열을 나누는 과정에서 나누어진 배열을 별도로 저장할 공간이 필요하다.
Stable 알고리즘	같은 값의 데이터의 기존 순서 유지를 보장할 수 있다.

 

병합 정렬의 시간  / 공간 복잡도는 아래와 같다.

알고리즘	시간복잡도(최상)	시간복잡도(평균)	시간복잡도(최악)	공간복잡도
병합 정렬	O(nlogn)	O(nlogn)	O(nlogn)	O(n)

 

병합 정렬은 다음과 같은 단계를 거쳐 완성된다. 기본적으로 2가지의 Phase를 갖는다 - Splitting / Merging

① Splitting - 분할

 - 정렬을 위해 준비를 하는 단계로 정렬되지 않은 배열 전체를 중앙을 중심으로 Left / Right로 나눈다.
 - 나누어진 배열을 인자가 1개 이하로 남을 때까지 지속하여 나눈다.
 - 재귀적으로 구현되기에 Left 배열이 모두 분할되고 난 뒤 Right 배열이 분할된다.

② Merging - 병합

 - 부분으로 나누어진 배열을 정렬하며 병합한다.
 - 1개의 전체 배열만 남을 때까지 지속하여 병합한다.

 

구현 코드는 다음과 같다.

public class MergeSort {
    public static void main(String[] args){
        int[] intArray = {20, 35, -15, 7, 55, 1, -22};


        mergeSort(intArray, 0, intArray.length);
        // 출력
        for(int i=0; i < intArray.length; i++){
            if(i == intArray.length-1){
                System.out.println(intArray[i]);
            } else {
                System.out.print(intArray[i] + ", ");
            }
        }
    }

    // 병합 정렬 구현하는 메소드
    public static void mergeSort(int[] intArray, int start, int end){

        // recursive 기반이므로 method 호출을 멈추는 breaking point가 필요
        // 배열에 남은 인자가 하나라면 더 이상 나눌 필요 없음. 해당 조건 명시
        if( end - start < 2) {
            return;
        }

        // 배열을 2가지로 나눌 기준을 정함
        int mid = (start + end) / 2;

        // left 부분을 기반으로 mergeSort 메소드 호출
        mergeSort(intArray, start, mid);

        // right 부분을 기반으로 mergeSort 메소드 호출
        mergeSort(intArray, mid, end);

        // partitioning 된 배열을 기반으로 병합 수행
        merge(intArray, start, mid, end);
    }

    // 실제로 병합을 수행하는 메소드
    public static void merge(int[] intArray, int start, int mid, int end){

        // mid-1인 경우는 left의 마지막 element
        // mid는 right의 최초 element
        // 이 경우 다음 조건에 해당한다면, left의 모든 정렬된 배열의 인자값이
        // right의 배열의 인자보다 작거나 같으므로 더 이상 정렬을 수행할 이유가 없다는 것
        if(intArray[mid - 1] <= intArray[mid]){
            return;
        }

        int i = start;
        int j = mid;
        int tempIndex = 0;

        int[] temp = new int[end - start];

        // i값은 mid보다 작다는 것은 left index의 최대 까지 증가할 수 있다는 의미
        // j값이 end 보다 작다는 조건은 right index의 최대 까지 증가할 수 있다는 의미
        // 그 조건이 만족되는 동안, i와 j의 index의 배열을 검사하여 정렬하고
        // 맞는 element를 임시 배열에 넣고 해당 index에 해당하는 변수의 값을 1 증가시킴
        while( i < mid && j < end){
            temp[tempIndex++] = intArray[i] <= intArray[j] ? intArray[i++] : intArray[j++];
        }

        // 위의 반복문을 이용해서 모든 index가 조정된 것은 아니므로 나머지 element를 정렬해야 한다.
        // right 쪽에 남아있는 경우에는 어차피 가장 큰 값이므로 또 다시 복사되지 않아도 상관없음
        // 그러나 left 쪽에 남아 있는 경우에는 position이 변경되어야 하므로 처리해야함
        // 그러므로, index 위치 i에서 시작하여 mid - i 부분의 길이(해당 길이는, mid와 i 사이에 남은 left 배열의 인자 개수)만큼 임시 배열에 저장된 마지막 index+1의 부분에 복사함.
        System.arraycopy(intArray, i, intArray, start + tempIndex, mid - i);

        // 그리고 전체 임시배열의 내용을 본래 배열에 전체 복사
        System.arraycopy(temp, 0, intArray, start, tempIndex);
    }
}

 

코드를 보면 크게 어렵지 않게 이해할 수 있습니다.

하지만, 간결한 코드로 보자면 다음과 같이 구현할 수 있습니다. 아래에서는 랜덤한 0~99의 100개의 숫자를 무작위로 넣고 정렬하도록 구현했습니다.

 

public class MergeSort{
    public static void main(String[] args){
        int[] arr = new int[100];
        for(int i=0; i < arr.length; i++){
            arr[i] = (int)(Math.random() * 100);
        }
        
        mergeSort(arr, 0, arr.length-1);
        for(int i=0; i < arr.length; i++){
            System.out.print(arr[i] + ", ");
        }
    }
    
    public static void mergeSort(int[] arr, int start, int end){
        if(start == end) return;
        
        int mid = (start+end)/2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid+1, end);
        
        int[] temp = new int[end-start+1];
        int idx = 0;
        int left = start;
        int right = mid+1;
        while(left <= mid && right <= end){
            temp[idx++] = arr[left] <= arr[right] ? arr[left++] : arr[right++];
        }
        while(left <= mid){
            temp[idx++] = arr[left++];
        }
        while(right <= end){
            temp[idx++] = arr[right++];
        }
        for(int i=start; i <= end; i++){
            arr[i] = temp[i-start];
        }
    }
}

 

 

오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.