20.06.24 개발일지 - 수 정렬하기 3

오늘은 Merge Sort를 구현해 보았습니다만 Memory 초과로 인해 통과하지 못했습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void MergeSort(vector<int>& List)
{
    if (List.size() < 5)
    {
        make_heap(List.begin(), List.end());
        sort_heap(List.begin(), List.end());
    }
    else
    {
        vector<int> front(List.begin(), List.begin() + List.size() / 2);
        vector<int> end(List.begin() + List.size() / 2, List.end());
        List.clear();
        MergeSort(front);
        MergeSort(end);
        for (unsigned int frontIndex = 0, endIndex = 0; frontIndex + endIndex < front.size() + end.size();)
        {
            if (frontIndex >= front.size())
            {
                List.push_back(end[endIndex++]);
            }
            else if (endIndex >= end.size())
            {
                List.push_back(front[frontIndex++]);
            }
            else
            {
                List.push_back(front[frontIndex] < end[endIndex] ? front[frontIndex++] : end[endIndex++]);
            }
        }
    }
}

int main()
{
    int size = 0, temp = 0;
    vector<int> list;
    
    cin >> size;
    for (unsigned int i = 0; i < size; ++i)
    {
        cin >> temp;
        list.push_back(temp);
    }

    MergeSort(list);
    
    for (const auto& iter : list)
    {
        cout << iter << endl;
    }
}

 

코드를 보면 알다싶이 재귀문에서 vector를 새로 생성하고 있습니다.

아마 이 때문에 문제가 생긴 것 같습니다.

내일은 이것을 하나의 Vector만 사용하여 Memory를 최소한으로 사용하는 Merge Sort로 고쳐보겠습니다.