[c++] 병합 정렬

12 Dec 2023

병합 정렬은 주어진 배열을 작은 부분 배열로 나눈 뒤, 이를 순서대로 합쳐 정렬하는 알고리즘입니다. 이를 C++로 구현하여보겠습니다.

병합 정렬 알고리즘

병합 정렬 알고리즘은 대개 재귀적인 방식으로 구현됩니다. 주어진 배열을 반으로 나누고, 각각을 재귀적으로 정렬한 뒤, 정렬된 부분 배열을 합쳐 전체 배열을 정렬합니다. 알고리즘의 핵심은 배열을 나누고 합치는 과정입니다.

#include <iostream>
using namespace std;

void merge(int arr[], int left, int middle, int right) {
    int n1 = middle - left + 1;
    int n2 = right - middle;

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[middle + 1 + j];
    }

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int middle = left + (right - left) / 2;

        mergeSort(arr, left, middle);
        mergeSort(arr, middle + 1, right);

        merge(arr, left, middle, right);
    }
}

정렬 결과 확인

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arrSize = sizeof(arr) / sizeof(arr[0]);

    cout << "정렬 전 배열: ";
    for (int i = 0; i < arrSize; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    mergeSort(arr, 0, arrSize - 1);

    cout << "정렬 후 배열: ";
    for (int i = 0; i < arrSize; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

위 코드는 입력으로 주어진 배열을 병합 정렬을 사용하여 오름차순으로 정렬한 결과를 보여줍니다.

병합 정렬은 안정적인 정렬 알고리즘으로, 데이터의 분포와 관계없이 항상 일정한 시간 복잡도를 갖는다는 장점이 있습니다. 그러나 메모리를 많이 사용하고 추가적인 배열을 필요로 한다는 단점도 있습니다.

이상으로 C++로 병합 정렬을 구현하고 정렬 결과를 확인하는 방법에 대해 알아보았습니다.

병합 정렬 알고리즘

정렬 결과 확인

참고 자료