Java에서 정렬 병합

1. 소개

이 튜토리얼에서는 Merge Sort 알고리즘과 Java에서의 구현을 살펴 보겠습니다 .

병합 정렬은 가장 효율적인 정렬 기술 중 하나이며 "분할 및 정복"패러다임을 기반으로합니다.

2. 알고리즘

병합 정렬은 먼저 문제를 하위 문제로 나누는 "분할 및 정복"알고리즘입니다. 하위 문제에 대한 솔루션이 준비되면이를 결합하여 문제에 대한 최종 솔루션을 얻습니다.

이것은 우리가 주요 문제가 아닌 하위 문제를 다룰 때 재귀를 사용하여 쉽게 구현할 수있는 알고리즘 중 하나입니다.

알고리즘은 다음 2 단계 프로세스로 설명 할 수 있습니다.

  • 나누기 :이 단계에서는 입력 배열을 절반으로 나눕니다 . 피벗은 배열의 중간 점입니다. 이 단계는 분할 할 절반 배열이 더 이상 없을 때까지 모든 절반 배열에 대해 반복적으로 수행됩니다.
  • 정복 :이 단계에서는 분할 된 배열 을 아래에서 위로 정렬하고 병합 하여 정렬 된 배열을 얻습니다.

다음 다이어그램은 예제 어레이 {10, 6, 8, 5, 7, 3, 4}에 대한 전체 병합 정렬 프로세스를 보여줍니다.

다이어그램을 자세히 살펴보면 배열이 크기가 1이 될 때까지 반복적으로 두 개의 절반으로 나뉘는 것을 볼 수 있습니다. 크기가 1이되면 병합 프로세스가 작동하여 정렬하는 동안 배열 병합을 시작합니다.

3. 구현

구현 을 위해 입력 배열과 그 길이 를 매개 변수로 받는 mergeSort 함수를 작성합니다 . 이것은 재귀 함수이므로 기본 및 재귀 조건이 필요합니다.

기본 조건은 배열 길이가 1인지 확인하고 반환합니다. 나머지 경우에는 재귀 호출이 실행됩니다.

재귀의 경우 중간 인덱스를 얻고 두 개의 임시 배열 l []r []을 만듭니다. 머지 소트의 기능은 다음 두 하위 배열에 대한 재귀 적으로 호출됩니다

public static void mergeSort(int[] a, int n) { if (n < 2) { return; } int mid = n / 2; int[] l = new int[mid]; int[] r = new int[n - mid]; for (int i = 0; i < mid; i++) { l[i] = a[i]; } for (int i = mid; i < n; i++) { r[i - mid] = a[i]; } mergeSort(l, mid); mergeSort(r, n - mid); merge(a, l, r, mid, n - mid); }

그런 다음 입력과 하위 배열, 두 하위 배열의 시작 및 끝 인덱스를 모두받는 merge 함수 를 호출합니다 .

병합 기능은 모두 하나의 서브 어레이를 하나의 소자와 비교하여 상기 입력 배열 작은 소자를 놓는다.

하위 배열 중 하나의 끝에 도달하면 다른 배열의 나머지 요소가 입력 배열로 복사되어 최종 정렬 된 배열이됩니다.

public static void merge( int[] a, int[] l, int[] r, int left, int right) { int i = 0, j = 0, k = 0; while (i < left && j < right) { if (l[i] <= r[j]) { a[k++] = l[i++]; } else { a[k++] = r[j++]; } } while (i < left) { a[k++] = l[i++]; } while (j < right) { a[k++] = r[j++]; } } 

프로그램의 단위 테스트 :

@Test public void positiveTest() { int[] actual = { 5, 1, 6, 2, 3, 4 }; int[] expected = { 1, 2, 3, 4, 5, 6 }; MergeSort.mergeSort(actual, actual.length); assertArrayEquals(expected, actual); }

4. 복잡성

병합 정렬은 재귀 알고리즘이므로 시간 복잡도는 다음과 같은 재귀 관계로 표현할 수 있습니다.

T(n) = 2T(n/2) + O(n)

2T (n / 2) 는 하위 배열을 정렬하는 데 필요한 시간과 전체 배열을 병합하는 데 O (n) 시간에 해당합니다.

해결되면 시간 복잡도가 O (nLogn)가됩니다.

이것은 항상 배열을 둘로 나눈 다음 병합하기 때문에 최악, 평균 및 최상의 경우에 해당됩니다.

알고리즘의 공간 복잡성은 모든 재귀 호출에서 임시 배열을 생성하므로 O (n) 입니다.

5. 결론

이 빠른 튜토리얼에서는 병합 정렬 알고리즘의 작동과이를 Java에서 구현하는 방법을 살펴 보았습니다.

전체 작업 코드는 GitHub에서 사용할 수 있습니다.