[c++] 반복 합병 정렬

12 Dec 2023

반복 합병 정렬은 합병 정렬을 반복문을 사용하여 구현한 정렬 알고리즘입니다. 이 알고리즘은 입력 크기에 관계없이 안정적이고 빠른 성능을 제공합니다.

알고리즘 설명

다음은 반복 합병 정렬의 간단한 설명입니다.

주어진 배열을 크기가 1인 작은 단위 배열로 분할합니다.
분할한 배열들을 순서대로 합병하여 크기가 2배씩 증가하는 정렬된 배열을 생성합니다.
이전 단계에서 생성한 정렬된 배열을 다시 크기가 2배씩 증가하는 정렬된 배열로 합병합니다. 이 과정을 반복하여 최종적으로 하나의 정렬된 배열을 생성합니다.

C++ 코드 예시

#include <iostream>
#include <vector>

void merge(std::vector<int>& arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    std::vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++) {
        L[i] = arr[l + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[m + 1 + j];
    }

    int i = 0, j = 0, k = l;
    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(std::vector<int>& arr) {
    int n = arr.size();
    for (int currSize = 1; currSize <= n - 1; currSize = 2 * currSize) {
        for (int leftStart = 0; leftStart < n - 1; leftStart += 2 * currSize) {
            int mid = std::min(leftStart + currSize - 1, n - 1);
            int rightEnd = std::min(leftStart + 2 * currSize - 1, n - 1);
            merge(arr, leftStart, mid, rightEnd);
        }
    }
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    int arrSize = arr.size();
    mergeSort(arr);
    std::cout << "Sorted array: ";
    for (int i = 0; i < arrSize; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

참고 자료

GeeksforGeeks “Iterative Merge Sort”: https://www.geeksforgeeks.org/iterative-merge-sort/
Cplusplus.com “Merge Sort”: http://www.cplusplus.com/forum/beginner/96031/

이와 같이 반복 합병 정렬은 입력된 배열을 효과적으로 정렬할 수 있는 강력한 알고리즘입니다.