[c++] 가용합병 정렬

12 Dec 2023

가용합병 정렬은 주어진 문제에 대해 최선의 알고리즘을 선택하여 적용함으로써 중간 크기의 배열에 대한 정렬이 더욱 효율적으로 수행됩니다. 이는 입력 크기에 따라 알고리즘을 동적으로 변경하여 최적의 성능을 얻는 것입니다.

가용합병 정렬의 시간 복잡도는 O(n log n)이며, 최악의 경우와 평균 경우가 모두 같은 시간복잡도를 갖습니다.

다음은 C++에서 가용합병 정렬을 구현한 간단한 예제입니다:

#include <iostream>
#include <algorithm>

const int INSERTION_THRESHOLD = 10;

template <typename T>
void insertionSort(T arr[], int start, int end) {
    for (int j = start + 1; j < end; j++) {
        T key = arr[j];
        int i = j - 1;
        while (i >= start && arr[i] > key) {
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = key;
    }
}

template <typename T>
void merge(T arr[], int start, int mid, int end) {
    int leftSize = mid - start + 1;
    int rightSize = end - mid;
    T leftArr[leftSize], rightArr[rightSize];
    for (int i = 0; i < leftSize; i++) {
        leftArr[i] = arr[start + i];
    }
    for (int j = 0; j < rightSize; j++) {
        rightArr[j] = arr[mid + j + 1];
    }

    int i = 0, j = 0, k = start;
    while (i < leftSize && j < rightSize) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }
    while (i < leftSize) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }
    while (j < rightSize) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

template <typename T>
void adaptiveMergeSort(T arr[], int start, int end) {
    if (end - start <= INSERTION_THRESHOLD) {
        insertionSort(arr, start, end);
    } else {
        int mid = start + (end - start) / 2;
        adaptiveMergeSort(arr, start, mid);
        adaptiveMergeSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}

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

    std::cout << "Sorted array: ";
    for (int i = 0; i < arrSize; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

이 코드는 가용합병 정렬을 구현하고, 작은 크기의 배열에 대해 삽입 정렬을 사용하여 성능을 최적화합니다.