Merge Sort 합병 정렬

 

효율적인 정렬을 위한 강력한 무기, 합병 정렬

프로그래밍 분야에서 정렬 알고리즘은 매우 중요한 위치를 차지합니다. 데이터를 특정 순서로 정렬하는 것은 다양한 문제를 해결하는 데 필수적입니다. 이러한 정렬 알고리즘 중 하나인 머지 소트(Merge Sort)는 분할 정복(Divide and Conquer) 기법을 활용하여 효율적이고 안정적인 정렬을 수행합니다.

728x90

작동 원리 살펴보기

머지 소트는 다음과 같은 세 단계로 진행됩니다.

1. 분할(Divide)

먼저, 정렬해야 할 배열을 두 개의 서브 배열로 나눕니다. 이 과정을 재귀적으로 반복하여 배열의 크기가 1이 될 때까지 계속 분할합니다. 배열의 크기가 1이 되면 더 이상 나눌 수 없으므로, 이를 기저 조건(base case)으로 합니다.

2. 정복(Conquer)

나누어진 각각의 서브 배열을 재귀적으로 정렬합니다. 배열의 크기가 1일 경우, 정렬된 상태이므로 그대로 둡니다.

3. 결합(Combine)

정렬된 서브 배열들을 다시 하나의 배열로 합칩니다. 이 과정에서 두 서브 배열의 원소들을 비교하며 정렬된 순서대로 새로운 배열에 넣습니다. 이렇게 하면 전체 배열이 정렬된 상태가 됩니다.

반응형

장점과 활용 분야

머지 소트는 다음과 같은 장점을 가지고 있습니다.

1. 안정적인 정렬

동일한 값을 가진 원소들의 상대적인 위치가 정렬 후에도 유지됩니다. 이는 정렬 과정에서 중요한 부가 정보가 손실되지 않도록 해줍니다.

2. 효율적인 대규모 데이터 정렬

머지 소트는 배열의 크기에 관계없이 O(n log n)의 시간 복잡도를 가집니다. 이는 대규모 데이터 집합에 대해서도 효율적으로 작동할 수 있음을 의미합니다.

3. 예측 가능한 실행 시간

배열의 초기 상태(정렬 여부, 역순 등)와 무관하게 일정한 실행 시간을 가지므로, 성능을 예측하기 쉽습니다.

4. 병렬 처리 가능

분할 단계에서 서브 배열들을 독립적으로 처리할 수 있기 때문에, 멀티 코어 시스템에서 병렬 처리가 가능합니다. 이를 통해 성능을 더욱 향상시킬 수 있습니다.

이러한 장점들 덕분에 머지 소트는 다양한 분야에서 활용됩니다. 특히 외부 정렬(external sorting)에 적합하며, 연결 리스트(linked list)에 대한 정렬에서도 효율적입니다.

단점과 대안

머지 소트의 가장 큰 단점은 추가적인 메모리 공간이 필요하다는 점입니다. 정렬 과정 중 임시 배열을 생성하기 때문에, 공간 복잡도가 O(n)이 됩니다. 따라서 메모리 제약이 있는 환경에서는 적절하지 않을 수 있습니다.

또한, 작은 배열에 대해서는 단순 정렬 알고리즘(예: 삽입 정렬, 선택 정렬)이 더 빠를 수 있습니다. 그러므로 데이터 크기에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.

이러한 단점을 극복하기 위해, 일부 구현에서는 작은 배열에 대해서는 단순 정렬을 사용하고, 큰 배열에 대해서만 머지 소트를 사용하는 하이브리드 접근법을 취합니다. 또한, 메모리 효율성을 높이기 위해 in-place 알고리즘을 사용하는 방법도 있습니다.

정리

머지 소트는 분할 정복 기법을 활용하여 효율적이고 안정적인 정렬을 수행하는 알고리즘입니다. 대규모 데이터 정렬, 외부 정렬, 병렬 처리 등 다양한 상황에서 유용하게 사용될 수 있습니다. 물론 추가 메모리 사용과 같은 단점도 있지만, 이를 보완하기 위한 여러 기법들이 존재합니다.

정렬 알고리즘은 프로그래밍의 기초 중 하나이며, 머지 소트는 그 중에서도 중요한 위치를 차지합니다. 머지 소트의 원리와 장단점을 이해함으로써, 보다 효율적인 코드를 작성하고 적절한 상황에서 활용할 수 있을 것입니다.

 

<Python 예제 코드>

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    return merge(left_half, right_half)

def merge(left, right):
    result = []
    left_idx = right_idx = 0

    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] <= right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1

    result.extend(left[left_idx:])
    result.extend(right[right_idx:])

    return result

# Example usage
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(arr)
print(sorted_arr)

 

<C++ 예제 코드>

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<int> L(n1), R(n2);

    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    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(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

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

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

int main() {
    vector<int> arr = { 64, 34, 25, 12, 22, 11, 90 };

    mergeSort(arr, 0, arr.size() - 1);

    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

 

<퀵 정렬 Quick Sort>

https://tonnykang.tistory.com/183

퀵 정렬 퀵 소트 quick sort