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

합병정렬 (merge sort)

개념

• 배열을 절반으로 나누어 각각을 정렬한 후, 합치는 정렬 알고리즘
• 시간 복잡도는 O(n log n) 이다.

처리과정

1. 정렬을 해야할 배열을 절반으로 나누어 왼쪽 배열 오른쪽 배열을 정렬한다.
2. 정렬된 왼쪽 배열 오른쪽 배열을 순서대로 합친다.

위의 처리과정을 크게 두가지로 나눌 수 있다. 

그럼.. 첫번째 순서에서 절반으로 나뉘어진 왼쪽 배열 오른쪽 배열의 정렬을 어떻게 정렬 할것인가? 라는 의문이 생기는데

그 절반으로 나뉘어진 두 배열도 똑같이 또 절반으로 나누고 정렬된 배열을 순서대로 합치면 된다.

그렇다는것은 재귀적으로 절반으로 나뉘어지지 않을때까지 배열이 나뉘어질 것이고 그 순간부터 하나하나 나뉘어진 배열을 합치면서 정렬이 진행된다.

정확한 순서는 아래 애니메이션을 보면 코드는 감이 안올지 몰라도 과정만큼은 감이 올것이라 생각한다.

구현하기

• 소스로 구현함에 있어서 합병정렬의 처리과정이 재귀적으로 동작한다는것을 이해해야한다.
• 재귀함수를 작성할때 재귀함수의 디자인 조건에 맞게 함수를 작성하면 어렵지(?) 않게 소스를 작성할 수 있다고 한다..

1. 작성하려는 함수의 역할을 말로 명확하게 정의한다.
   
   

   // arr 을 s 번째 값 부터 e 번째 값까지 합병 정렬하는 함수
   public void mergeSort(int arr[], int s, int e){
    
   }

2. 함수가 기저조건에서 제대로 동작하게 작성한다.
   
   

   // arr 을 s 번째 값 부터 e 번째 값까지 합병 정렬하는 함수
   public void mergeSort(int arr[], int s, int e){
       // 시작 인덱스가 끝 인덱스보다 같거나 클 수가 없다.
       if( s >= e) {
           return;
       }
   }

3. 함수가 제대로 동작한다고 가정하고 함수를 완성한다.
   
   

   // arr 을 s 번째 값 부터 e 번째 값까지 합병 정렬하는 함수
   public void mergeSort(int arr[], int s, int e){
       // 시작 인덱스가 끝 인덱스보다 같거나 클 수가 없다.
       if( s >= e) {
           return;
       }
    
       int middle = (s+e) / 2;
       mergeSort(arr, s, middle);      // 왼쪽 절반 정렬
       mergeSort(arr, middle+1, e);  // 오른쪽 절반 정렬
       merging(s, mid, mid+1, e);     // 합치기(왼쪽 절반 범위 인덱스, 오른쪽 절반 범위 인덱스)
   }
    
   public void merging(int s1, int e1, int s2, int e2) {
    // 두 배열의 인덱스 정보로 왼쪽, 오른쪽 정렬을 합치는 과정
   }

소스 ( JAVA )

MergeSort 라는 클래스를 만들고 MergeSort 객체를 생성해서 mergeSort() Method를 호출하면 된다.
이번에는 좀 길다.

import java.util.Arrays;
 
public class SortMain {
    
    public static void main(String[] args) {
        int[] intArr01 = { 25, 90, 11, 3, 2, 6, 9, 33, 10, 25 };
        int[] intArr02 = { 90, 111, 2, 2, 44, 5, 3, 222, 1, 2, 30, 50, 222, 10, 20, 66, 3, 30, 10, 250, 243, 565, 31, 10, 200 };
        
        // 합병 정렬
        int[] mergeSortArr = intArr02.clone();
        MergeSort mergeSort = new MergeSort();
        mergeSort.mergeSort(mergeSortArr, 0, mergeSortArr.length-1);
        
        System.out.println("Merge Sort : " + Arrays.toString(mergeSortArr));
    }
}
 
 
public class MergeSort {
    public void mergeSort(int[] arr, int start, int end) {
        // arr의 start부터 end 까지를 합병정렬하는 Method
        
        if(start >= end) {
            return;
        }
        // 1. 왼쪽 절반 합병정렬
        // 2. 오른쪽 절반 합병정렬
        // 3. 왼쪽절반 오른쪽 절반을 합친다.
        int mid = (start + end) / 2;
        this.mergeSort(arr, start, mid);
        this.mergeSort(arr, mid+1, end);
        
        // arr[start~mid], arr[mid+1 ~ end] 는 정렬이 이미 되어 있음
        this.merging(arr, start, mid, mid+1, end);
    }
    
    public void merging(int[] arr, int s1, int e1, int s2, int e2) {
        // arr의 s1~e1 이 왼쪽 절반, 
        // arr의 s2~e2 가 오른쪽 절반
        // 이둘을 합쳐서 arr의 s1~e2를 정렬된 결과로 만드는 함수
        int p, q; // 왼쪽과 오른쪽의 현재 최소값을 가리키는 변수
        int temp[] = new int[(e2-s1)+1]; //합쳐진 결과를 저장하는 임시변수 
        int temp_inx = 0;
        
        p = s1;
        q = s2;
        // p 와 q 가 모두 각각의 범위안에 있어야 한다.
        while(p <= e1 && q <= e2) {
            if(arr[p] <= arr[q]) {
                temp[temp_inx++] = arr[p++];
            }else {
                temp[temp_inx++] = arr[q++];
            }
        }
        //    한쪽 인덱스가 범위를 초과 했을때 나머지 한쪽의 값들을 전부 temp 배열에 추가한다.
        if(p > e1) { // 왼쪽은 전부 정렬된 상태 오른쪽 나머지 temp 배열에 추가
            for(int i=q; i<=e2; i++) {
                temp[temp_inx++] = arr[i]; 
            }
        }else {// 오른쪽은 전부 정렬된 상태 왼쪽 나머지 temp 배열에 추가
            for(int i=p; i<=e1; i++) {
                temp[temp_inx++] = arr[i];
            }
        }
        // temp arr이 완성됨
        // arr[s1~e2] 까지에 temp의 값을 복사
        for(int i=s1; i<=e2; i++) {
            arr[i] = temp[i-s1];
        }
    }
}