[기초] C++ 알고리즘 : 병합 정렬 (Merge Sort)

---

 

병합 정렬(Merge Sort)은 효율적인 정렬 알고리즘 중 하나로,

분할 정복(divide and conquer) 방식을 이용합니다.

이 알고리즘의 기본 원리는 큰 문제를 작은 문제로 나누어 해결한 후,

그 해결된 결과들을 합쳐 전체 문제의 해답을 얻는 것입니다.

 

---

 

#include <iostream>

using namespace std;

// 병합 함수
void merge(int arr[], int const left, int const mid, int const right) {
    auto const subArrayOne = mid - left + 1;
    auto const subArrayTwo = right - mid;

    // 임시 배열 생성
    int *leftArray = new int[subArrayOne],
        *rightArray = new int[subArrayTwo];

    // 데이터를 임시 배열로 복사
    for (auto i = 0; i < subArrayOne; i++)
        leftArray[i] = arr[left + i];
    for (auto j = 0; j < subArrayTwo; j++)
        rightArray[j] = arr[mid + 1 + j];

    auto indexOfSubArrayOne = 0, // 첫 번째 서브 배열의 초기 인덱스
        indexOfSubArrayTwo = 0; // 두 번째 서브 배열의 초기 인덱스
    int indexOfMergedArray = left; // 원래 배열에서 병합된 요소의 인덱스

    // 서브 배열 정렬 및 병합
    while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) {
        if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) {
            arr[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
            indexOfSubArrayOne++;
        } else {
            arr[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
            indexOfSubArrayTwo++;
        }
        indexOfMergedArray++;
    }
    // 남은 데이터 복사
    while (indexOfSubArrayOne < subArrayOne) {
        arr[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
        indexOfSubArrayOne++;
        indexOfMergedArray++;
    }
    while (indexOfSubArrayTwo < subArrayTwo) {
        arr[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
        indexOfSubArrayTwo++;
        indexOfMergedArray++;
    }

    delete[] leftArray;
    delete[] rightArray;
}

// 병합 정렬 함수
void mergeSort(int arr[], int const begin, int const end) {
    if (begin >= end)
        return; // 종료 조건

    auto mid = begin + (end - begin) / 2;
    mergeSort(arr, begin, mid);
    mergeSort(arr, mid + 1, end);
    merge(arr, begin, mid, end);
}

// 배열을 출력하는 함수
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 메인 함수
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "정렬 전 배열: ";
    printArray(arr, n);

    mergeSort(arr, 0, n - 1);

    cout << "정렬 후 배열: ";
    printArray(arr, n);

    return 0;
}

 

병합 함수는 주어진 배열의 'left', 'mid', 'right' 인덱스 사이의 요소들을 병합합니다.

배열은 두 부분으로 나뉘어져 있고 각 부분은 이미 정렬되어 있다고 가정합니다

 

• 두 개의 임시 배열 'leftArray'와 'rightArray'를 생성하고, 각각 정렬된 왼쪽 및 오른쪽 부분의 값을 복사합니다.
• 두 임시 배열의 요소를 비교하면서, 더 작은 값을 원래의 배열로 복사합니다.
  이렇게 함으로써 정렬된 큰 배열을 만듭니다.
• 두 임시 배열 중 한쪽의 요소가 남아 있을 수 있으므로, 이를 원래 배열에 순차적으로 복사합니다.
• 동적으로 할당한 임시 배열의 메모리를 해제합니다.

병합 정렬 함수는 재귀적으로 배열을 분할하고, 각 부분을 정렬한 후 병합합니다.

 

• 배열을 반으로 나눕니다. 중간 지점 'mid'는 시작점 'begin'과 끝점 'end'를 사용하여 계산합니다.
• 왼쪽 부분 배열과 오른쪽 부분 배열을 각각 재귀적으로 정렬합니다.
• 정렬된 두 부분 배열을 병합합니다.

 

출력 결과

 

정렬 전 배열: 12 11 13 5 6 7
정렬 후 배열: 5 6 7 11 12 13

 

 

 

제 글이 도움이 되셨다면 댓글 & 공감 부탁드려요 😀