C++에서 병합 정렬 알고리즘 구현
이 기사에서는 C++에서 병합 정렬 알고리즘을 구현하는 방법을 소개합니다.
C++에서std::vector컨테이너에 대한 병합 정렬 구현
병합 정렬은 분할 및 정복 전략을 활용하여 효율성을 높이고 큰 목록에 대한 범용 정렬 알고리즘으로 사용할 수 있습니다. 알고리즘의 기본 개념은 입력 벡터를 여러 개의 작은 벡터로 나눈 다음 각 벡터를 정렬하는 것입니다. 더 작은 벡터가 완료되면 상대적으로 더 간단한 작업 인 단일 목록으로 병합 할 수 있습니다. 다음 코드 예제는이 솔루션에 가장 적합하므로 재귀를 사용하여이 메서드를 구현합니다. 재귀 프로세스는 비교 함수가 호출되는 두 요소 벡터를 얻을 때까지 원래 벡터를 여러 번 나누는 데 사용됩니다. 각 쌍이 정렬되면 요소가 4 개인 벡터로 병합되는 방식으로 최종 재귀 수준이 반환 될 때까지 계속됩니다.
mergeSort함수는 재귀 프로세스의 핵심 부분입니다. 벡터 참조를 유일한 인수로 취하고 크기가 1보다 작은 지 확인합니다. 그렇다면 벡터는 정렬 된 벡터로 한정되고 함수는 반환됩니다. 벡터에 두 개 이상의 요소가 포함 된 경우 두 개의 개별 벡터 개체로 분할되고 각각에 대해mergeSort함수가 호출됩니다. 후반부는 가장 작은 부분 벡터에서 정렬이 시작되도록합니다. 재귀가 이러한 수준에 도달하면mergeSort함수가 모두 반환되고 다음 코드가 실행을 시작합니다. 처음에는vec벡터가 지워진 다음merge함수가 호출됩니다. merge기능은 면밀한 관찰로 그로 킹 할 수있는 반복적 인 프로세스로 구현됩니다. 일반적으로 마지막 단계에서는 정렬 된 가장 작은 벡터를 하나의 벡터 객체로 결합합니다.
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void merge(vector<T> &vec, vector<T> &v1, vector<T> &v2) {
auto siz1 = v1.size();
auto siz2 = v2.size();
size_t p1 = 0;
size_t p2 = 0;
while (p1 < siz1 && p2 < siz2) {
if (v1.at(p1) < v2.at(p2))
vec.push_back(v1.at(p1++));
else
vec.push_back(v2.at(p2++));
}
while (p1 < siz1) vec.push_back(v1.at(p1++));
while (p2 < siz2) vec.push_back(v2.at(p2++));
}
template <typename T>
void mergeSort(vector<T> &vec) {
if (vec.size() <= 1) return;
auto iter = vec.begin() + vec.size() / 2;
vector<T> v1(vec.begin(), iter);
vector<T> v2(iter, vec.end());
mergeSort(v1);
mergeSort(v2);
vec.clear();
merge(vec, v1, v2);
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
mergeSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
출력:
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
또는 읽기 코드를 단순화 할 수있는 STL std::merge알고리즘을 사용하여 이전 코드를 다시 작성할 수 있습니다. std::merge함수는merge구현을 대체하고 벡터 병합은mergeSort함수 본문의 단일 명령문으로 수행 할 수 있습니다. 최종 재귀 수준이mergeSort의 첫 번째 호출에서 두 개의 벡터를 반환 할 때std::merge의 마지막 호출은main함수에서 관찰 할 수있는 원래vec객체에 정렬 된 내용을 저장합니다.
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void mergeSort2(vector<T> &vec) {
if (vec.size() <= 1) return;
auto iter = vec.begin() + vec.size() / 2;
vector<T> v1(vec.begin(), iter);
vector<T> v2(iter, vec.end());
mergeSort2(v1);
mergeSort2(v2);
vec.clear();
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
std::back_inserter(vec));
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
mergeSort2(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
경험적 타이밍 측정으로 병합 정렬 복잡성 분석
병합 정렬은 O (n log n) 최악의 실행 시간을 제공하며, 이는 현대의 범용 정렬 알고리즘 중에서 가장 좋은 것 중 하나입니다. 빠른 정렬 알고리즘이 제공하는 것보다 더 많은 최악의 시나리오에서 선형 공간 복잡성이 있습니다. 후자는 구현이 피벗 변수를 선택하는 효율적인 방법을 사용할 때 실제로 상대적으로 더 빠른 경향이 있습니다.
재귀 적 방법은 이해하기가 매우 까다로울 수 있지만, 항상 디버거를 사용하여 각 단계의 핵심을 살펴볼 수 있습니다. 그러나 상위 수준에서는 다음 코드 샘플을 사용하여 서로 다른 벡터 크기 사이의 재귀 함수 호출을 계산할 수 있습니다. 재귀 호출의 합은 함수-2n - 2가되는 경향이 있습니다. 여기서n은 벡터의 요소 수에 해당합니다.
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void mergeSort2(vector<T> &vec, int &level) {
if (vec.size() <= 1) return;
auto iter = vec.begin() + vec.size() / 2;
vector<T> v1(vec.begin(), iter);
vector<T> v2(iter, vec.end());
mergeSort2(v1, ++level);
mergeSort2(v2, ++level);
vec.clear();
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(),
std::back_inserter(vec));
}
int main() {
vector<int> vec3(100, 10);
vector<int> vec4(200, 10);
int recursion_level = 0;
mergeSort2(vec3, recursion_level);
cout << "recursion level: " << recursion_level << endl;
recursion_level = 0;
mergeSort2(vec4, recursion_level);
cout << "recursion level: " << recursion_level << endl;
return EXIT_SUCCESS;
}
출력:
recursion level: 198
recursion level: 398
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook