Merge Algorithm - 병합 알고리즘

Merge Algorithm - 병합 알고리즘

• 오름차순으로 정렬되어 있는 두 정수 배열을 하나로 병합

package mergeAlgorithm;
//[?] 2개의 정수 배열 합치기 : 단 2개의 배열은 오름차순으로 정렬되어 있다고 가정

//병합 알고리즘(Merge Algorithm) : 오름차순으로 정렬되어 있는 정수 배열을 하나로 병합

public class MergeAlgorithm {
	public static void main(String[] args) {
		//[1] input
		int[] first = {1, 3, 5};
		int[] second = {2, 4};
		int M=first.length; int N=second.length; // 관행 적으로 배열은 M, N으로 많이 표현함
		int[] merge = new int[M+N]; 		// 병합된 배열
		int i = 0, j = 0, k = 0; 		// 관행적으로 정수는 i, j, k 등으로 많이 표현
		
		//[2] process : 병합 알고리즘
		while (i < M && j < N) {		// 둘 중 하나라도 배열의 끝에 도달할 때까지
			if(first[i] < second[j]) {	//작은 값을 merge 배열에 저장
				merge[k++] = first[i++];
			} else {
				merge[k++]=second[j++];
			}
		}
		while (i<M) {			//첫 번째 배열이 끝까지 도달할 때까지
			merge[k++]=first[i++];
		}
		while (j<N) {			//두 번째 배열이 끝까지 도달할 때까지
			merge[k++]=second[j++];
		}
		
		//[3] output
		for(int ii = 0; ii<M+N; ii++) {
			System.out.print(merge[ii] + " ");
		}
		System.out.println();
		/* 아래 처럼 for-each문으로도 가능.
		for(int item : merge) {
			System.out.print(item + " ");
		}
		System.out.println();
		*/
	}
}