[java] 자바에서 병합 정렬 구현하기

15 Dec 2023

java

병합 정렬은 배열을 작은 크기의 배열로 나눈 뒤, 이를 병합하여 정렬하는 방식입니다. 자바에서는 이를 구현하기 위한 다양한 방법이 있습니다. 이번 포스트에서는 배열을 병합 정렬하는 간단한 예제 코드를 제시하겠습니다.

병합 정렬 알고리즘 개요

병합 정렬의 주요 단계는 다음과 같습니다.

분할(Divide): 배열을 같은 크기의 두 하위 배열로 분할합니다.
정복(Conquer): 각 하위 배열을 재귀적으로 병합 정렬합니다.
병합(Merge): 정렬된 하위 배열을 다시 하나로 병합합니다.

이러한 단계를 통해 정렬되지 않은 배열을 정렬된 배열로 만들 수 있습니다.

자바로 병합 정렬 구현하기

아래는 자바를 사용한 간단한 병합 정렬 구현 예제 코드입니다.

public class MergeSort {
    public 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];

        for (int i = 0; i < n1; ++i) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; ++j) {
            R[j] = arr[mid + 1 + j];
        }

        int i = 0, j = 0;

        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

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

    public void sort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;

            sort(arr, left, mid);
            sort(arr, mid + 1, right);

            merge(arr, left, mid, right);
        }
    }

    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        System.out.println("정렬 전 배열: " + Arrays.toString(arr));

        MergeSort ms = new MergeSort();
        ms.sort(arr, 0, arr.length - 1);

        System.out.println("병합 정렬 후 배열: " + Arrays.toString(arr));
    }
}

마치며

위 예제 코드는 병합 정렬을 사용하여 배열을 정렬하는 방법을 보여줍니다. 이를 통해 병합 정렬 알고리즘을 이해하고 코드로 구현하는 방법을 학습할 수 있습니다.

병합 정렬은 대부분의 경우에 효율적으로 작동하며, 안정적인 정렬 알고리즘 중 하나로 널리 사용됩니다.

더 많은 자바 정렬 알고리즘에 대해 알고 싶다면 Java Sorting Algorithms를 참고하세요.

이상으로 병합 정렬 알고리즘에 대한 자바 구현 예제를 살펴보았습니다. 감사합니다.