자료구조 - 합병 정렬

[합병 정렬(Merge Sort)]

합병 정렬(Merge Sort)은 분할 정복 알고리즘의 하나로, 리스트를 반으로 나누어 각각을 정렬한 다음, 합병하여 전체 리스트를 정렬하는 방법입니다.

재귀적인 구조를 가지며, 리스트의 길이가 1이 될 때까지 계속하여 반으로 나누고, 나중에 합병하면서 정렬합니다. 합병 정렬은 안정적인 정렬 알고리즘이며, 시간 복잡도는 항상 O(nlogn) 입니다.

 

 

합병 정렬 과정

1. 리스트를 반으로 나눕니다.
2. 각 부분 리스트를 재귀적으로 합병 정렬을 호출하여 정렬합니다.
3. 정렬된 부분 리스트를 합병하여 전체 리스트를 정렬합니다.

 

 

합병 정렬 의사 코드

함수 mergeSort(arr):
    if 리스트의 길이(arr) <= 1:
        반환 arr

    // 리스트를 반으로 나눔
    mid = 리스트의 길이(arr) / 2
    left_half = arr의 처음부터 mid까지의 부분 리스트
    right_half = arr의 mid부터 끝까지의 부분 리스트

    // 각 부분 리스트를 재귀적으로 정렬
    left_half = mergeSort(left_half)
    right_half = mergeSort(right_half)

    // 정렬된 부분 리스트를 합병하여 정렬
    반환 merge(left_half, right_half)

함수 merge(left, right):
    result = 빈 배열
    while left와 right가 비어있지 않은 동안:
        if left의 첫 번째 요소 <= right의 첫 번째 요소:
            result에 left의 첫 번째 요소를 추가하고 left에서 삭제
        else:
            result에 right의 첫 번째 요소를 추가하고 right에서 삭제

    // 남은 요소들을 추가
    result += left
    result += right

    반환 result

 

 

합병 정렬 예제

예시 리스트: [64, 25, 12, 22, 11]

첫 번째 재귀 호출:
    리스트를 반으로 나누어 각각 [64, 25], [12, 22, 11]로 분할합니다.
    각 부분 리스트를 재귀적으로 정렬합니다.

두 번째 재귀 호출:
    [64, 25]를 정렬하여 [25, 64]로 반환합니다.    
    [12, 22, 11]를 정렬하여 [11, 12, 22]로 반환합니다.

합병 과정:
    [25, 64]와 [11, 12, 22]를 합병하여 정렬합니다.

결과: [11, 12, 22, 25, 64]

 

 

합병 정렬 코드

#include <iostream>
#include <vector>

using namespace std;

// 두 개의 정렬된 부분 리스트를 합병하여 정렬된 리스트를 반환
vector<int> merge(vector<int>& left, vector<int>& right) 
{
    vector<int> result;
    int left_index = 0, right_index = 0;

    // left와 right가 비어있지 않은 동안 반복
    while (left_index < left.size() && right_index < right.size()) 
    {
        if (left[left_index] <= right[right_index]) 
        {
            result.push_back(left[left_index]);
            left_index++;
        } 
        else 
        {
            result.push_back(right[right_index]);
            right_index++;
        }
    }

    // 남은 요소들을 추가
    while (left_index < left.size()) 
    {
        result.push_back(left[left_index]);
        left_index++;
    }
    while (right_index < right.size()) 
    {
        result.push_back(right[right_index]);
        right_index++;
    }

    return result;
}

// 합병 정렬 함수
vector<int> mergeSort(vector<int>& arr) 
{
    int n = arr.size();

    // 리스트의 길이가 1 이하이면 그대로 반환
    if (n <= 1)
    {
        return arr;
    }

    // 리스트를 반으로 나눔
    int mid = n / 2;
    vector<int> left_half(arr.begin(), arr.begin() + mid);
    vector<int> right_half(arr.begin() + mid, arr.end());

    // 각 부분 리스트를 재귀적으로 정렬
    left_half = mergeSort(left_half);
    right_half = mergeSort(right_half);

    // 정렬된 부분 리스트를 합병하여 반환
    return merge(left_half, right_half);
}

int main() 
{
    vector<int> arr = {64, 25, 12, 22, 11};  // 예제 리스트

    cout << "정렬 전: ";
    for (int i : arr) 
    {
        cout << i << " ";
    }
    cout << endl;

    arr = mergeSort(arr);  // 합병 정렬 수행

    cout << "정렬 후: ";
    for (int i : arr) 
    {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}