[C++][구현] Merge Sorted (배열 문제)

 

이미 정렬된 Array1과, Array2가 있습니다.

Array1에는 Array2이 들어갈 숫자만큼 0이란 숫자로 채워져 있는 공간이 있습니다.

Array1과, Array2를 서로 비교해가며, Array1에 두 배열을 합친 값이 sorted된 배열을 만드는 문제입니다.

 

Array3이란 따른 배열을 추가하여 처음부터 비교해가면서 구하는 방법 이외로 Array1에 그대로 넣는다는 점이 흥미롭습니다.

void mergeSorted(int nums1[], int n, int nums2[], int m) {
	int num1Idx = n - 1;
	int num2Idx = m - 1;
	int wIdx = n + m - 1;

	if (num2Idx < 0) return;

	while (0 <= num1Idx && 0 <= num2Idx) {
		
		int num1 = nums1[num1Idx];
		int num2 = nums2[num2Idx];

		if (num2 <= num1) {
			int num = num1;
			nums1[wIdx] = num;
			--wIdx;
			--num1Idx;
		}
		else {
			int num = num2;
			nums1[wIdx] = num;
			--wIdx;
			--num2Idx;
		}

	}

	while (0 <= num2Idx) {
		nums1[wIdx] = nums2[num2Idx];
		--wIdx;
		--num2Idx;
	}
}

 

 

서로 비교해가는 num1Idx, num2Idx를 통하여 비교를 하고,

쓰기위한 wIdx를 통해 배열을 고쳐나가면 됩니다.