자바 병합(Merge) 알고리즘 정리

병합(Merge) 알고리즘은

오름차순으로 정렬되어 있는 정수 배열을

하나의 배열로 병합해주는 알고리즘인데

 

먼저 두 배열을 오름차순 정렬시킨 후

while을 돌려주면서 두 배열의 값을 비교해

작은 값을 반환시킬 배열에 넣어준다

 

해당 while은 한 배열의 끝까지만 도달해도

종료되는 조건이기 때문에

 

arr1의 1

arr2의 2

arr1의 3

arr2의 4

를 넣어주면

 

j가 2이기 때문에

i < arr1.length && j < arr2.length

조건을 충족시키지 못하기 때문에 종료되고

더 긴 배열인 arr1만 남게 되는데

 

이후 while을 돌려주면서

  arr1의 값을 쭉 넣어주면

오름차순으로 정렬했기 때문에

 

기존에 넣었던 값보다 더 큰 값이

차례대로 들어가게 된다

 

여기서 while(j<arr2.length)

를 왜 하나 이런 의문이 들 수 있는데

당장은 필요가 없지만 알고리즘 문제를 풀거나 할 경우

 

더 긴 배열은 언제든지 바뀔 수 있기 때문에

해당 케이스를 위해서 작성을 해 놓은 것이다

 

정리해보자면 병합 알고리즘은

두 배열을 오름차순으로 정렬한 후

한 배열이 끝날 때까지

비교해서 작은 값을 먼저 넣어주고

마지막으로 남은 배열의 값을 넣어주면 된다

 

예제에 사용한 코드는 아래와 같다

 

	public static void main(String[] args) {
		// 병합 알고리즘(Merge Algorithm)
		// 오름차순으로 정렬되어 있는 정수 배열을 하나로 병합(미리 오름차순 정렬 필요)
		int[] arr1 = {1, 3, 5};
		int[] arr2 = {2, 4};
		int[] answer = new int[arr1.length + arr2.length];
		int i = 0; int j = 0; int k = 0;
		
		while(i < arr1.length && j < arr2.length) { // 둘 중의 하나라도 배열 끝까지 갈 경우 종료
			if(arr1[i] < arr2[j]) { // 작은 값을 먼저 넣어줌
				answer[k++] = arr1[i++];
			} else {
				answer[k++] = arr2[j++];
			}
		}
		
		// 남은 배열(길이가 더 긴 배열)의 값을 넣어줌
		while(i < arr1.length) { // 첫 번째 배열이 끝까지 도달할 때가지
			answer[k++] = arr1[i++];
		}
		while(j < arr2.length) { // 두 번째 배열이 끝까지 도달할 때까지
			answer[k++] = arr2[j++];
		}
		
		for(int m = 0; m<answer.length; m++) {
			System.out.print(answer[m] + " "); // 병합된 배열 출력
		}			
	}