병합 알고리즘

merge_sort.c, 알고리즘_병합(MEARGE).c

/*
    병합(MEARGE) 알고리즘 : 오름차순으로 나열된 두 그룹의 데이터를 한 그룹의 데이터로 병합한다.
    (1) 데이터 a, b 중에 어느 한 쪽이 끝에 도달할 때까지 다음을 반복
    (2) a(i)와 b(j)를 비교해서 작은쪽을 c(k)에 복사하고 작은 쪽의 첨자를 +1한다.
    (3) 둘 중에 아직 끝까지 도달하지 않은 데이터를 끝까지 복사한다.
*/
#include <stdio.h>

#define M 10
#define N 5

int main(void)
{
    //[1] Init/Input
    static int a[] = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
    static int b[] = { 1, 3, 5, 7, 9 };
    static int c[M + N];. //병합된 데이터 저장

    //[2] Process
    int i, j, k;

    i = j = k = 0;

    while (i < M && j < N). //a[], b[] 모두 끝에 도달하지 않은 동안
    {
        if (a[i] <= b[j])
        {
            c[k++] = a[i++];
        }
        else
        {
            c[k++] = b[j++];
        }
    }

    while (i < M). . //a[]가 끝에 도달할 때까지
    {
        c[k++] = a[i++];
    }

    while (j < N). . //b[]가 끝에 도달할 때까지
    {
        c[k++] = b[j++];
    }

    //[3] Output
    for (i = 0; i < M + N; i++)
    {
        printf("%d ", c[i]);
    }
    printf("\n");

    return 0;
}

1 2 3 4 5 6 7 8 9 10 12 14 16 18 20

코드: MergeAlgorithm.cs

// MergeAlgorithm.cs
//[?] 2개의 정수 배열 합치기: 단, 2개의 배열은 오름차순으로 정렬되어 있다고 가정 
using System;

/// <summary>
/// 병합 알고리즘(Merge Algorithm): 오름차순으로 정렬되어 있는 정수 배열을 하나로 병합
/// </summary>
class MergeAlgorithm
{
    static void Main()
    {
        //[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; int j = 0; int k = 0; // i, j, k 관행

        //[2] Process: 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++];
        }

        //[3] Output
        foreach (var m in merge)
        {
            Console.Write($"{m}\t");
        }
        Console.WriteLine();
    }
}

1       2       3       4       5

다음 코드를 사용하면 중간 단계를 표시할 수 있습니다.

코드: MergeAlgorithmTest.cs

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

/// <summary>
/// 병합 알고리즘(Merge Algorithm): 오름차순으로 정렬되어 있는 정수 배열을 하나로 병합
/// </summary>
class MergeAlgorithmTest
{
    static void Main()
    {
        int count = 0; 
        //[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; int j = 0; int k = 0; // i, j, k 관행

        count = PrintStep(count, merge, i, j, k);

        //[2] Process: MERGE
        while (i < M && j < N) // 둘 중 하나라도 배열의 끝에 도달할 때까지
        {
            if (first[i] <= second[j]) // 더 작은 값을 merge 배열에 저장
            {
                merge[k++] = first[i++]; // 작은 값 대입 후 각각의 인덱스 증가
            }
            else
            {
                merge[k++] = second[j++]; // 작은 값 대입 후 각각의 인덱스 증가
            }

            count = PrintStep(count, merge, i, j, k);
        }
        while (i < M) // 첫 번째 배열이 끝까지 도달할 때까지
        {
            merge[k++] = first[i++];
            count = PrintStep(count, merge, i, j, k);
        }
        while (j < N) // 두 번째 배열이 끝까지 도달할 때까지
        {
            merge[k++] = second[j++];
            count = PrintStep(count, merge, i, j, k);
        }
    }

    private static int PrintStep(int count, int[] merge, int i, int j, int k)
    {
        Console.WriteLine($"{count++}회전");
        Console.WriteLine($"\ti: {i}, j: {j}, k: {k}, merge: {String.Join(",", merge)}");
        return count;
    }
}

0회전
        i: 0, j: 0, k: 0, merge: 0,0,0,0,0
1회전
        i: 1, j: 0, k: 1, merge: 1,0,0,0,0
2회전
        i: 1, j: 1, k: 2, merge: 1,2,0,0,0
3회전
        i: 2, j: 1, k: 3, merge: 1,2,3,0,0
4회전
        i: 2, j: 2, k: 4, merge: 1,2,3,4,0
5회전
        i: 3, j: 2, k: 5, merge: 1,2,3,4,5

참고: LINQ로 데이터 병합하기

LINQ와 람다 식을 사용하여 2개의 정수 배열을 병합하려면 다음처럼 메서드 구문이나 쿼리 구문을 사용하면 됩니다.

코드: MergeAlgorithm.cs

// MergeAlgorithm.cs
> int[] first = { 1, 3, 5 };
> int[] second = { 2, 4 };
> int[] merge =
.     (from o in first select o).Union(from t in second select t)
.     .OrderBy(m => m).ToArray();
> merge
int[5] { 1, 2, 3, 4, 5 }
> int[] merge = first.Union(second).OrderBy(m => m).ToArray();
> merge
int[5] { 1, 2, 3, 4, 5 }

PrimeNumber.java

// MergeAlgorithm.java

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: 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++];
        }

        //[3] Output
        for (int m : merge) {
            System.out.print(m + "\t");
        }
        System.out.println();
    }
}

prime_number.py

# MergeAlgorithm.py

# [1] Input
first = [1, 3, 5]  # 오름차순 정렬됨
second = [2, 4]  # 오름차순 정렬됨
M = len(first)
N = len(second)  # M:N 관행
merge = [0] * (M + N)  # 병합된 배열
i, j, k = 0, 0, 0  # i, j, k 관행

# [2] Process: MERGE
while i < M and j < N:  # 둘 중 하나라도 배열의 끝에 도달할 때까지
    if first[i] <= second[j]:  # 작은 값을 merge 배열에 저장
        merge[k] = first[i]
        k += 1
        i += 1
    else:
        merge[k] = second[j]
        k += 1
        j += 1
while i < M:  # 첫 번째 배열이 끝까지 도달할 때까지
    merge[k] = first[i]
    k += 1
    i += 1
while j < N:  # 두 번째 배열이 끝까지 도달할 때까지
    merge[k] = second[j]
    k += 1
    j += 1

# [3] Output
for m in merge:
    print(m, end='\t')
print()

https://www.dotnetkorea.com/BoardView?BoardName=Qna&Num=1039

merge[k] = first[i];
k++;
i++;

위 세 줄을 한 줄로 줄인 코드가 다음 코드입니다.

merge[k++] = first[i++];

병합 정렬 알고리즘은 이미 정렬된 두 개의 배열을 합쳐서 그 결괏값도 정렬된 형태로 나오는게 목적입니다. 제가 책에도 썼지만, 12개 알고리즘은 공식과 같은 알고리즘이기에, 수학 공식 암기 형태로 익혀두시면 좋습니다. 그리고, Visual Studio 2022에서 F11번 계속 반복하면서 실행해보시면 코드 흐름을 익히는데 도움이 되실 겁니다.