31.11 배열을 하나로 합치기: MERGE 알고리즘
병합(MERGE) 알고리즘은 배열 2개를 합쳐 하나로 만듭니다.
병합 알고리즘 사용하기
다음 예제는 오름차순으로 정렬된 두 정수 배열을 병합합니다. 처리 조건은 다음과 같습니다.
• first 배열은 1~M, second 배열은 1~N 자료가 있습니다.
• merge 배열은 M + N개가 있습니다.
• i, j, k는 배열 첨자 변수로 사용됩니다.
다음 내용을 입력한 후 실행해 보세요.
오름차순으로 정렬된 두 정수 배열 병합: MergeAlgorithm.cs
using System;
class MergeAlgorithm
{
static void Main()
{
//① 입력
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; int j = 0; int k = 0; //i, j, k 관행
//② 처리: MERGE
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++];
}
//③ 출력
foreach (var m in merge)
{
Console.Write($"{m}\t");
}
Console.WriteLine();
}
}
실행 결과
1 2 3 4 5
병합 알고리즘(병합 정렬 알고리즘) 공식과 같은 코드 형태입니다. 코드 내 주석을 읽으면서 직접 입력한 후 결과를 확인하길 권장합니다.