초보 자바 프로그래밍(21) - 병합정렬 (Merge Sort)

병합 정렬 대표 이미지

🔖 INDEX

• 병합 정렬의 작동 원리
• 병합 정렬의 특징
• 병합 정렬의 구현 예제

 

 

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 방식을 사용하는 비교 기반 정렬 알고리즘입니다. 병합 정렬은 배열을 두 개의 동일한 크기의 하위 배열로 분할한 다음, 하위 배열을 정렬한 후 다시 병합하는 과정을 통해 정렬을 수행합니다. 병합 정렬은 안정적이며, 빠르게 작동하므로 큰 데이터 셋에 적합한 알고리즘입니다.

 

병합 정렬의 작동 원리

병합 정렬의 작동 원리는 다음과 같습니다:

1. 배열의 크기가 1 또는 0이 될 때까지 배열을 절반으로 나누어 재귀적으로 분할합니다.
2. 분할된 하위 배열을 정렬하고 병합하는 과정을 시작합니다. 이 때 하위 배열의 크기가 1이면 이미 정렬된 것으로 간주합니다.
3. 두 개의 인접한 정렬된 하위 배열을 병합하여 새로운 정렬된 배열을 만듭니다. 병합 과정에서 두 하위 배열의 원소들을 비교하며 작은 값을 새 배열에 삽입하고, 해당 원소를 원래 하위 배열에서 삭제합니다. 이 과정을 두 하위 배열의 모든 원소가 새 배열에 삽입될 때까지 반복합니다.
4. 모든 하위 배열이 병합되어 원래 배열의 크기와 동일한 크기의 정렬된 배열이 완성될 때까지 이 과정을 반복합니다.

 

병합 정렬의 특징

병합 정렬의 특징은 다음과 같습니다:

1. 안정적인 정렬(Stable Sort): 같은 값의 원소들은 정렬 과정에서 상대적인 순서가 변경되지 않습니다.
2. 비제자리 정렬(Out-of-place Sort): 정렬 과정에서 추가적인 메모리를 사용합니다. 이는 병합 과정에서 두 하위 배열을 새로운 배열에 합치는 과정에서 발생합니다.
3. 시간 복잡도(Time Complexity): 최선, 평균, 최악의 경우 모두 O(n log n)의 시간 복잡도를 가집니다. 이로 인해 큰 데이터 셋에 적합한 알고리즘입니다.
4. 재귀적(Recursive): 병합 정렬은 재귀적으로 배열을 분할하고 병합하는 과정을 수행합니다.

병합 정렬은 큰 데이터 셋에서 빠른 성능을 보이지만, 추가적인 메모리 사용량이 비교적 높습니다. 이 때문에 메모리 제약이 있는 상황에서는 다른 알고리즘을 사용하는 것이 좋습니다. 예를 들어, 퀵 정렬과 힙 정렬은 추가 메모리 사용량이 적은 대안이 될 수 있습니다.

 

 

병합 정렬의 장점

• 안정적인 정렬: 같은 값의 원소들은 정렬 과정에서 상대적인 순서가 변경되지 않습니다.
• 큰 데이터 셋에 효율적: 병합 정렬은 O(n log n)의 시간 복잡도를 가지므로 큰 데이터 셋에서도 빠른 성능을 보입니다.
• 고르게 분할된 작업: 병합 정렬은 배열을 고르게 분할하여 작업을 수행하므로 최악의 경우에도 균일한 성능을 보입니다.

 

병합 정렬의 단점

• 추가 메모리 사용: 병합 정렬은 두 하위 배열을 새로운 배열에 합치는 과정에서 추가적인 메모리를 사용합니다. 이로 인해 메모리 제약이 있는 상황에서는 더 적합한 알고리즘을 선택하는 것이 좋습니다.
• 재귀적 구현: 병합 정렬은 재귀적으로 구현되어 있으므로, 스택 오버플로와 같은 문제가 발생할 수 있습니다. 이를 방지하기 위해 반복적인 구현 방법도 사용할 수 있습니다.

 

병합 정렬의 구현 예제

병합 정렬은 자바에서 다음과 같이 구현할 수 있습니다.

 

 

// MergeSort 클래스 선언
public class MergeSort {
    // 병합 과정을 수행하는 함수
    public static void merge(int[] arr, int left, int middle, int right) {
        // 구간의 크기를 계산
        int n1 = middle - left + 1;
        int n2 = right - middle;

        // 임시 배열 생성
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        // 원래 배열에서 임시 배열로 데이터 복사
        System.arraycopy(arr, left, leftArr, 0, n1);
        System.arraycopy(arr, middle + 1, rightArr, 0, n2);

        // 인덱스 초기화
        int i = 0, j = 0, k = left;
        
        // 두 배열을 비교하면서 병합
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i++];
            } else {
                arr[k] = rightArr[j++];
            }
            k++;
        }

        // 왼쪽 배열에 남은 원소를 복사
        while (i < n1) {
            arr[k++] = leftArr[i++];
        }

        // 오른쪽 배열에 남은 원소를 복사
        while (j < n2) {
            arr[k++] = rightArr[j++];
        }
    }

    // 병합 정렬 알고리즘을 수행하는 함수
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            // 중간 인덱스 계산
            int middle = (left + right) / 2;
            // 왼쪽 부분 배열 정렬
            mergeSort(arr, left, middle);
            // 오른쪽 부분 배열 정렬
            mergeSort(arr, middle + 1, right);
            // 병합
            merge(arr, left, middle, right);
        }
    }

    // 메인 함수
    public static void main(String[] args) {
        // 정렬할 배열
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        // 정렬 전 배열 출력
        System.out.println("Unsorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }

        // 병합 정렬 실행
        mergeSort(arr, 0, arr.length - 1);

        // 정렬 후 배열 출력
        System.out.println("\nSorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }
}

병합 정렬은 재귀적 구현이 일반적이기 때문에 재귀 호출에 대한 깊이 제한이 적용되어 있을 경우, 깊이 제한에 도달하기 전에 정렬이 완료되지 않을 수 있습니다. 이 경우 반복적인 구현 방법을 사용하거나, 깊이 제한을 적절히 조절해야 합니다.

 

또한, 메모리 사용량이 큰 편이므로 메모리 제약이 있는 시스템에서 사용하기에는 부적합할 수 있습니다. 이러한 상황에서는 퀵 정렬, 힙 정렬 등 메모리 사용량이 상대적으로 적은 정렬 알고리즘을 고려해 볼 수 있습니다.