#include <iostream>
#include <vector>
uaing namespace std;
template<typename T>
vector<T> merge(vector<T>& arr1, vector<T>& arr2)
{
vector<T> merged;
auto iter1 = arr1.begin();
auto iter2 = arr2.begin();
while (iter1 != arr1.end()&&iter2 != arr2.end())
{
if (*iter1 < *iter2)
{
merged.emplace_back(*iter1);
iter1++;
}
else
{
merged.emplace_back(*iter2);
iter2++;
}
}
if (iter1 != arr1.end())
{
for (; iter1 != arr1.end(); iter1++)
merged.emplace_back(*iter1);
}
else
{
for (; iter2 != arr2.end(); iter2++)
merged.emplace_back(*iter2);
}
return merged;
}
template<typename T>
vector<T> merge_sort(vector<T> arr)
{
if (arr.size() > 1)
{
auto mid = size_t(arr.size() / 2);
auto left_half = merge_sort<T>(vector<T>(arr.begin(), arr.begin() + mid));
auto right_half = merge_sort<T>(vector<T>(arr.begin() + mid, arr.end()));
return merge<T>(left_half, right_half);
}
return arr;
}
template<typename T>
void print_vector(std::vector<T> arr)
{
for (auto i : arr)
cout << i << " ";
cout << endl;
}
void run_merge_sort_test()
{
vector<int> S1{ 45, 1, 3, 1, 2, 3, 45, 5, 1, 2, 44, 5, 7 };
vector<float> S2{ 45.6f, 1.0f, 3.8f, 1.01f, 2.2f, 3.9f, 45.3f, 5.5f, 1.0f, 2.0f, 44.0f, 5.0f, 7.0f };
vector<double> S3{ 45.6, 1.0, 3.8, 1.01, 2.2, 3.9, 45.3, 5.5, 1.0, 2.0, 44.0, 5.0, 7.0 };
vector<char> S4{ 'b', 'z', 'a', 'e', 'f', 't', 'q', 'u', 'y'};
cout << "정렬되지 않은 입력 벡터:" << endl;
print_vector<int>(S1);
print_vector<float>(S2);
print_vector<double>(S3);
print_vector<char>(S4);
cout << endl;
auto sorted_S1 = merge_sort<int>(S1);
auto sorted_S2 = merge_sort<float>(S2);
auto sorted_S3 = merge_sort<double>(S3);
auto sorted_S4 = merge_sort<char>(S4);
cout << "병렬 정합에 의해 정렬된 벡터:" << endl;
print_vector<int>(sorted_S1);
print_vector<float>(sorted_S2);
print_vector<double>(sorted_S3);
print_vector<char>(sorted_S4);
cout << endl;
}
int main()
{
run_merge_sort_test();
return 0;
}
각각의 함수에 대한 간단한 설명을 하겠습니다.
1. vector<T> merge(vector<T>& arr1, vector<T>& arr2)
해당 함수는 우선 전달인자로 두 배열을 받습니다. 그 후 다음의 절차를 진행합니다.
그 후 함수의 반환형인 vector함수의 형태로 merge배열을 반환합니다.
2. vector<T> merge_sort(vector<T> arr)
해당 함수는 배열의 원소가 1개를 가질때까지 배열의 가운데를 기준으로 쪼개서 배열이 한 개의 원소만을 가질때까지 분해한 후, 부분 집합들을 merge함수를 통해 정렬상태를 유지한 상태로 병합합니다.
3. void print_vector(vector<T> arr)
해당 함수는 배열의 시작 원소부터 마지막 원소까지 순서대로 출력하는 함수입니다.
4. void run_merge_sort_test()
해당 함수는 여러 정렬 알고리즘의 필수 3요소 중 모든 타입에 대해 동작하는지 알아보기 위해, 다양한 타입의 vector 배열을 merge_sort 함수를 사용해서 정렬하는 것을 시연하기 위해 만들어진 함수입니다.