자바 코딩테스트 강좌, 병합 정렬

알고리즘 문제를 풀기 위해서는 다양한 정렬 알고리즘을 이해하는 것이 중요합니다. 이 글에서는 병합 정렬의 개념과 자바 코드 구현을 통해 문제를 해결하는 과정을 알아보겠습니다.

문제 설명

다음과 같은 정수 배열이 주어졌을 때, 병합 정렬 알고리즘을 이용하여 배열을 오름차순으로 정렬하시오.

입력: [38, 27, 43, 3, 9, 82, 10]
출력: [3, 9, 10, 27, 38, 43, 82]

병합 정렬이란?

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 알고리즘의 일종입니다. 이 알고리즘은 대체로 다음과 같은 단계로 작동합니다:

주어진 배열을 반으로 나눕니다.
각 부분 배열을 재귀적으로 정렬합니다.
정렬된 두 부분 배열을 병합하여 하나의 정렬된 배열로 만듭니다.

병합 정렬의 시간 복잡도는 O(n log n)이며, 안정적인 정렬 알고리즘으로 분류됩니다.

병합 정렬의 구현 과정

1. 배열 분할

배열을 계속해서 반으로 나누어 작은 배열로 나갑니다. 이 단계는 배열의 크기가 1이 될 때까지 계속됩니다.

2. 병합 및 정렬

각각의 분할된 배열들이 정렬되면, 이들을 다시 합치는 과정이 필요합니다. 이 때 두 배열을 비교하여 정렬된 상태로 병합합니다.

3. 자바 코드 구현

이제 병합 정렬 알고리즘을 자바로 구현해 보겠습니다.

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("정렬 전: " + java.util.Arrays.toString(arr));
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("정렬 후: " + java.util.Arrays.toString(arr));
    }

    public static 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);
            // 병합
            merge(arr, left, mid, right);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        // 왼쪽과 오른쪽 부분의 크기 계산
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // 임시 배열 생성
        int[] L = new int[n1];
        int[] R = new int[n2];

        // 임시 배열에 데이터 복사
        System.arraycopy(arr, left, L, 0, n1);
        System.arraycopy(arr, mid + 1, R, 0, n2);

        // 병합하는 과정
        int i = 0, j = 0, k = left; // i는 왼쪽 배열 인덱스, j는 오른쪽 배열 인덱스
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }

        // 남아 있는 요소 복사
        while (i < n1) {
            arr[k++] = L[i++];
        }

        while (j < n2) {
            arr[k++] = R[j++];
        }
    }
}

코드 설명

위 코드는 병합 정렬 알고리즘을 구현한 것입니다. 각 부분을 살펴보면:

main 메서드: 배열을 초기화하고, 병합 정렬 메서드를 호출하여 정렬된 결과를 출력합니다.
mergeSort 메서드: 주어진 배열을 반으로 나누어 재귀적으로 정렬합니다.
merge 메서드: 두 개의 정렬된 배열을 병합하여 하나의 정렬된 배열로 만드는 역할을 합니다.

정리

병합 정렬은 안정적인 정렬 알고리즘으로, 대량의 데이터를 정렬하는 데 적합합니다. 자바로 구현함으로써 코드의 이해를 높이고, 실제 프로그래밍에 적용할 수 있는 기반을 마련했습니다. 병합 정렬 알고리즘을 통해 복잡한 데이터를 효과적으로 정렬하는 방법을 익히길 바랍니다.

문제 해결 및 테스트

자바로 구현한 병합 정렬을 통해 다양한 테스트 케이스를 시도해 보세요. 예를 들어, 이미 정렬된 배열, 역순으로 정렬된 배열, 중복 요소가 있는 배열 등 여러 가지 경우를 테스트하여 병합 정렬의 특성을 확인해 보세요.

응용 및 연습 문제

병합 정렬을 활용하여 다음과 같은 문제를 해결해 보세요:

주어진 배열에서 중복된 값을 제거한 후 정렬하는 프로그램을 작성하시오.
랜덤한 숫자로 이루어진 배열을 생성하고, 병합 정렬로 정렬한 후 결과를 출력하는 프로그램을 작성하시오.

이런 연습을 통해 병합 정렬의 이해도를 높이고 자바 코딩 실력을 향상시킬 수 있습니다.