[ch 10-2] 복잡하지만 효율적인 정렬 알고리즘_1(병합 정렬)

[주제]

- 병합 정렬에 대한 개념과 구현

[중요]

- 정렬의 과정 => 1단계: 복합(Divide) → 2단계: 정복(Conquer) → 3단계: 결합(Combine)

- 정렬할 배열을 중간을 기준으로 2개로 나눠서 따로 정렬

- 1:1로 비교될 때까지 분할

- 다시 거꾸로 숫자를 비교해가면서 정렬

  ※ 재귀

■ 그림(병합 정렬 과정)

- 숫자 '5, 7, 4, 2, 1, 8, 3, 6'을 오름차순으로 정렬

[소스]

■ Merge.java

package sortMerge;
 
public class Merge {
    
    public Merge() {}
    
    ///// 분할된 숫자들을 병합
    public void MergeTwoArea(int arr[], int left, int mid, int right) {
        
        int fIdx = left;        // 정렬할 배열의 왼쪽 영역 인덱스를 가리킴
        int rIdx = mid + 1;     // 정렬할 배열의 오른쪽 영역 인덱스를 가리킴
        
        int sortArr[] = new int[arr.length];    // 정렬한 숫자를 저장하는 공간
        int sIdx = left;        // 'sortArr'에 숫자가 저장되는 위치를 가리킴
        
/*
 * 중간을 기준으로 왼쪽 영역 숫자와 오른족 영역 숫자 비교
 * 왼쪽 또는 오른쪽 숫자 중 한 쪽 정렬이 끝날 때까지 반복
 */
        while (fIdx <= mid && rIdx <= right) {
            if (arr[fIdx] <= arr[rIdx]) {
                sortArr[sIdx] = arr[fIdx++];
            } else {
                sortArr[sIdx] = arr[rIdx++];
            }
            
            sIdx++;
        }
        
/*
 * 한쪽 영역의 숫자가 전부 정렬된 배열에 저장되었다면,
 * 반대 영역의 남은 숫자들을 정렬된 배열에 저장
 */
        if (fIdx > mid) {
            for (int i = rIdx; i <= right; i++, sIdx++) {
                sortArr[sIdx] = arr[i];
            }
        } else {
            for (int i = fIdx; i <= mid; i++, sIdx++) {
                sortArr[sIdx] = arr[i];
            }
        }
 
/*
 * 정렬된 배열의 숫자들을 다시 원래 배열 공간에 순서대로 저장        
 */
        for (int i = left; i <= right; i++) {
            arr[i] = sortArr[i];
        }
    }
    
/*
 * 더 이상 분할 할 수 없을 때까지 분할
 * ※ 1개가 남을 때까지
 */
    public void MergeSort(int arr[], int left, int right) {
        
        if (left < right) {
            int mid = (left+right) / 2;
            
            MergeSort(arr, left, mid);
            MergeSort(arr, mid+1, right);
            
            MergeTwoArea(arr, left, mid, right);
        }
    }
}

■ mainClass.java

package sortMerge;
 
public class mainClass {
    
    public static void main(String[] args) {
        
        Merge mcls = new Merge();
        
        int arr[] = { 5, 7, 4, 2, 1, 8, 3, 6 };
        
        mcls.MergeSort(arr, 0, arr.length-1);
        
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

■ 실행결과

[첨부 파일]

mainClass.java

Merge.java