[알고리즘] 분할정복 - 합병정렬(1)

분할정복의 개념을 잡기 위해 합병정렬 코드를 작성해보았다.

처음의 개념은 다음과 같다.

 

divide()라는 메소드를 생성하여 배열을 재귀적으로 나누는 것을 생각했다.

소스코드는 다음과 같다.

 private static void divide(int[] arr, int start, int end) {
        int mid;
        while(start<end) {
            mid = (start+end)/2;
            divide(arr,start,mid);
            divide(arr, mid+1, end);
        }
    }

배열과 처음과 끝 인덱스를 파라미터로 넣어서 재귀적으로 호출한다.

그런데 호출 후에 배열을 어떻게 정렬할지 생각했고 새로운 메소드를 만들어서 나눈 값들로 비교해서 그 값을 다시 합한 값을 리턴해야겠다 생각했다.

---

가령 예를 들어보자.

 

divide()는 재귀적으로 호출하기 때문에

 

divide(arr, 1, 4) -> divide(arr,1,2) divide(arr,3,5)

divide(arr, 5, 8) -> divide(arr, 5,6) divide(arr,6,8)

 

이렇게 된다. while문의 조건은 start<end 이므로 

divide(arr,1,2) -> divide(arr,1,1) divide(arr,2,2)  

divide(arr,5,6) -> divide(arr, 5,5) divide(,6,6)

이렇게 최종적으로 남게 된다.

 

이렇게 재귀적으로 나눈 후의 코드에서 합병하여 정렬하는 메소드를 호출하면 정렬된 배열을 호출할 수 있을 것이라 생각했다. 즉 while문 안에서 divide()를 호출을 나눠서 하고 호출된 코드 아래에 정렬하는 메소드를 하나 추가하고자 한다.

 

conq() 메소드를 생각하는 데에는 시간이 오래 걸렸지만 조각낸 divide 에서의 배열 인덱스를 생각했을 때 구현하기 쉬워졌다. 처음 생각한 구조는 다음과 같다.

private static void divide(int[] arr, int start, int end) {
        int mid;
        while(start<end) {
            mid = (start+end)/2;
            divide(arr,start,mid);
            divide(arr, mid+1, end);
            arr = conq(arr, start, mid, end);
        }
    }

    private static int[] conq(int[] arr, int start, int mid, int end) {
        int[] ans = new int[arr.length];
        int i=0;

        while(start<mid && mid+1<end) {
            if(arr[start]>arr[mid+1]) {
                ans[++i] = arr[++mid+1];
            } else {
                ans[++i] = arr[++start];
            }
        }
        return ans;
    }

주르륵 짰는데 빈 ans 배열에 각각 정렬한 것을 넣고 리턴을 한다면 값이 비어있기 때문에 arr에 넣게되면 문제가 생기지 않을까 생각했다.

당연히 그렇다.

추가하지 않은 배열이 빈 배열이기 때문에 arr에 ans를 넣어버리면 빈값이라 호출할 때 비교를 못하는 상황이 발생하게 된다.

 

case 1

그렇다면 ans에 배열을 새로 추가하지 않고

1. tmp 변수를 생성한 후에

2. 비교 값을 일단 tmp에 넣어둔 다음

3. 비교를 하는 것이 어떨까?

-> conq() 메소드에서 배열을 리턴할 필요도 없고 arr에 ans를 넣는 번거로움도 사라질 거 같다.

: 그런데 하나만 비교할 경우만 가능하지 여러 변수를 비교하는 것은 어려울 듯 하다.

 

조금 더 고민해보겠다....