Java에서 두 개의 정렬 된 배열을 병합하는 방법

1. 소개

이 자습서에서는 두 개의 정렬 된 배열을 단일 정렬 된 배열로 병합하는 방법을 알아 봅니다.

2. 문제

문제를 이해합시다. 두 개의 정렬 된 배열이 있으며이를 하나로 병합하고 싶습니다.

3. 알고리즘

문제를 분석 할 때 Merge Sort의 병합 연산을 사용하여이 문제를 해결할 수 있음을 쉽게 관찰 할 수 있습니다.

각각 길이가 fooLengthbarLength 인 두 개의 정렬 된 배열 foobar 가 있다고 가정 해 보겠습니다 . 다음으로 fooLength + barLength 크기의 병합 된 또 다른 배열을 선언 할 수 있습니다 .

그런 다음 동일한 루프에서 두 배열을 모두 탐색해야합니다. 각각 fooPositionbarPosition에 대한 현재 인덱스 값을 유지합니다 . 루프의 주어진 반복 에서 인덱스에 더 작은 값의 요소가있는 배열을 가져와 해당 인덱스를 전진시킵니다. 이 요소는 병합 된 배열 에서 다음 위치를 차지합니다 .

마지막으로 한 배열의 모든 요소를 ​​전송 한 후에는 나머지 요소를 병합 된 배열 로 복사합니다 .

이제 알고리즘을 더 잘 이해하기 위해 그림으로 프로세스를 살펴 보겠습니다.

1 단계:

두 배열의 요소를 비교하여 시작하고 더 작은 배열을 선택합니다.

그런 다음 첫 번째 배열 의 위치를 ​​증가시킵니다 .

2 단계:

여기서 두 번째 배열 의 위치를 ​​증가시키고 다음 요소 인 8로 이동합니다.

3 단계 :

이 반복이 끝나면 첫 번째 배열 의 모든 요소를 ​​탐색했습니다 .

4 단계 :

이 단계에서는 두 번째 배열 의 나머지 요소를 모두 result에 복사합니다 .

4. 구현

이제이를 구현하는 방법을 살펴 보겠습니다.

public static int[] merge(int[] foo, int[] bar) { int fooLength = foo.length; int barLength = bar.length; int[] merged = new int[fooLength + barLength]; int fooPosition, barPosition, mergedPosition; fooPosition = barPosition = mergedPosition = 0; while(fooPosition < fooLength && barPosition < barLength) { if (foo[fooPosition] < bar[barPosition]) { merged[mergedPosition++] = foo[fooPosition++]; } else { merged[mergedPosition++] = bar[barPosition++]; } } while (fooPosition < fooLength) { merged[mergedPosition++] = foo[fooPosition++]; } while (barPosition < barLength) { merged[mergedPosition++] = bar[barPosition++]; } return merged; }

그리고 간단한 테스트를 진행해 보겠습니다.

@Test public void givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray() { int[] foo = { 3, 7 }; int[] bar = { 4, 8, 11 }; int[] merged = { 3, 4, 7, 8, 11 }; assertArrayEquals(merged, SortedArrays.merge(foo, bar)); }

5. 복잡성

두 배열을 모두 탐색하고 더 작은 요소를 선택합니다. 결국 foo 또는 bar 배열 에서 나머지 요소를 복사합니다 . 따라서 시간 복잡도는 O (fooLength + barLength)가 됩니다. 결과를 얻기 위해 보조 배열을 사용했습니다. 따라서 공간 복잡성도 O (fooLength + barLength) 입니다.

6. 결론

이 튜토리얼에서는 정렬 된 두 배열을 하나로 병합하는 방법을 배웠습니다.

평소처럼이 튜토리얼의 소스 코드는 GitHub에서 찾을 수 있습니다.