(C/C++) 병합정렬 Merge Sort

#병합 #정렬 #머지소트 #C언어 #배열 #Array

 

 

병합정렬(Merge Sort)

이미 정렬되어 있는 2개 이상의 부분 집합들을 크기순으로 한 개로 합치는 것을 말합니다.

 

 

C언어 코드

#include <stdio.h>
#define NA 10
#define NB 5
#define NC (NA+NB)

int main()
{
    int a[NA] = { 11,22,33,44,55,66,77,88,87,88 };
    int b[NB] = { 10,30,35,78,90 };
    int c[NC];
    int i, j, p;

    i = j = p = 0;
    while (i < NA && j < NB) {        // a, b 둘 중 한 개가 먼저 끝날때까지 반복
        if (a[i] <= b[j])
            c[p++] = a[i++];
        else
            c[p++] = b[j++];
    }

    while (i < NA)                // a 나머지가 있으면 끝에 추가
        c[p++] = a[i++];
    while (j < NB)                // b 나머지가 있으면 끝에 추가
        c[p++] = b[j++];

    for (i = 0; i < NC; i++)      // 병합된 배열 출력
        printf("%d ", c[i]);
    printf("\n");

    return 0;
}

 

 

 

 

C++ 코드

#include <iostream>
using namespace std;

int main()
{
    const int NA = 10;
    const int NB = 5;
    const int NC = NA+NB;

    int a[NA] = { 1,22,33,44,55,66,77,88,87,88 };
    int b[NB] = { 11,30,35,78,90 };
    int c[NC];
    int i, j, p;

    i = j = p = 0;
    while (i < NA && j < NB) {      
        if (a[i] <= b[j])
            c[p++] = a[i++];
        else
            c[p++] = b[j++];
    }

    while (i < NA)               
        c[p++] = a[i++];
    while (j < NB)           
        c[p++] = b[j++];

    for (i = 0; i < NC; i++)
        cout << c[i] << " ";
    cout << endl;

    return 0;
}