[Algorithm] 두 배열을 정렬하며 합치기 : 병합 정렬 기초

인트로

병합 정렬을 포스팅하기 앞서 병합 정렬의 핵심 로직인 두 배열을 정렬하며 합치는 과정을 기록하려 한다.

 

보다 쉬운 이해를 위해 두 배열을 정렬하며 합치는 문제를 소개하려 한다.

 

↓병합정렬 포스팅↓

[Algorithm] 병합 정렬(Merge Sort) 코드와 시간 복잡도

[Algorithm] 병합 정렬(Merge Sort) 코드와 시간 복잡도

 

두 배열 합치기 

문제

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.

※ 입력설명
첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.
네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 배열의 원소는 int형 변수의 크기를 넘지 않습니다.

※ 출력설명
오름차순으로 정렬된 배열을 출력합니다.

입력

3
1 3 5
5
2 3 6 7 9

출력

1 2 3 3 5 6 7 9

코드 설명

#include <iostream>

using namespace std;

int main()
{
	int n, m, p1 = 1, p2 = 1, p3 = 1;
	int a[101], b[101], res[201];

	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	cin >> m;
	for (int i = 1; i <= m; i++)
		cin >> b[i];

	while (p1 <= n && p2 <= m)
	{
		if (a[p1] < b[p2])
			res[p3++] = a[p1++];
		else
			res[p3++] = b[p2++];
	}

	while (p1 <= n)
		res[p3++] = a[p1++];
	while (p2 <= m)
		res[p3++] = b[p2++];

	for (int i = 1; i <= n + m; i++)
		cout << res[i] << " ";
}