병합 정렬 알고리즘 이해(Java 예제 포함)

병합 정렬: 종합 가이드

병합 정렬은 다양한 프로그래밍 언어에서 독립적으로 또는 하이브리드 접근 방식의 일부로 자주 사용되는 매우 효율적인 정렬 알고리즘입니다. 그 기반은 분할 및 정복 패러다임에 있습니다. 문제는 더 작은 하위 문제로 나누어 개별적으로 해결되고 최종 결과를 위해 해당 솔루션이 결합됩니다. 병합 정렬은 입력 목록을 반복적으로 절반으로 나누고 각 절반을 정렬한 다음 정렬된 절반을 병합하여 완전히 정렬된 목록을 생성합니다.

병합정렬 과정의 이해

예제 배열을 사용하여 병합 정렬 프로세스를 설명해 보겠습니다.

이 이미지는 배열의 재귀적 분할을 보여줍니다.

이 이미지는 정렬된 하위 배열의 병합을 보여줍니다.

병합 정렬 구현

다음은 병합 정렬 알고리즘의 Java 구현입니다.

import java.util.Arrays;

public class MergeSortTest {
    public static void main(String[] args){
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length-1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    static void mergeSort(int arr[], int start, int end){
        if (start < end){
            int mid = (start + end) / 2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid + 1, end);
            merge(arr, start, mid, end);
        }
    }

    static void merge(int arr[], int start, int mid, int end){
        int[] left = new int[(mid - start) + 1];
        int[] right = new int[end - mid];

        for(int i = 0; i <= mid - start; i++)
            left[i] = arr[start + i];
        for(int j = 0; j < end - mid; j++)
            right[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int k = start;

        while (i < left.length && j < right.length){
            if(left[i] <= right[j]){
                arr[k] = left[i];
                i++;
            }
            else{
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < left.length){
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < right.length){
            arr[k] = right[j];
            j++;
            k++;
        }
    }
}

코드 설명

mergeSort 메서드는 하위 배열에 요소가 하나만 포함될 때까지 배열을 재귀적으로 나눕니다. merge 방법이 중요합니다. 정렬된 하위 배열을 가져와 효율적으로 단일 정렬 배열로 병합합니다. 병합 프로세스에는 두 하위 배열의 요소를 비교하고 더 작은 요소를 기본 배열에 배치하는 작업이 포함됩니다.

이 이미지는 병합 단계를 보여줍니다.

코드 출력은 다음과 같습니다.

정렬되지 않은 배열: [8, 2, 6, 4, 9, 1] 정렬된 배열: [1, 2, 4, 6, 8, 9]

알고리즘의 복잡성

• 시간 복잡도: 모든 경우(최상, 평균, 최악)에서 O(n log n)입니다. 이는 분할 정복 접근 방식이 입력 배열의 초기 순서에 관계없이 일관되게 유지되기 때문입니다.
• 공간 복잡도: 병합 작업 중 임시 배열에 필요한 추가 공간으로 인해 O(n)

위 내용은 병합 정렬 알고리즘 이해(Java 예제 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!