Является ли стандартная реализация сортировки слиянием предпочтительнее реализации, написанной с использованием векторов?

Я изучаю алгоритмы и пытаюсь найти собственную реализацию сортировки слиянием. Я написал следующую реализацию.

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

vector<int> merge(vector<int> A, vector<int> B)
{
int n1 = A.size();
int n2 = B.size();
vector<int> result;
int i = 0;
int j = 0;
while(i < n1 && j < n2)
{
if(A[i] < B[j])
{
result.push_back(A[i]);
i++;
}
else
{
result.push_back(B[j]);
j++;
}
}
while(i<n1){
result.push_back(A[i]);
i++;
}
while(j<n2){
result.push_back(B[j]);
j++;
}
return result;
}

vector<int> mergeSort(vector<int> M){
int n = M.size();
if (n==1){ return M; }
else {
vector<int> A;
vector<int> B;
int m = floor(n/2);
for(int i = 0; i<m; i++){ A.push_back(M[i]);}
for(int j =m;j<n; j++){ B.push_back(M[j]);}
return merge(mergeSort(A), mergeSort(B));
}
}

int main(){
static const int arr1[] = {5332, 52, -41, 421, 54, 865, 987, 698430, -54670, -5436, 990};
vector<int> A (arr1, arr1 + sizeof(arr1)/sizeof(arr1[0]));
vector<int> C = mergeSort(A);
for(vector<int>::const_iterator i = C.begin();i != C.end(); ++i){ cout << *i << " ";  }
cout << "\n";
return 0;   }

Затем, когда я вышел в Интернет, чтобы увидеть стандартную реализацию MergeSort, она сильно отличалась от моей. Хотя они реализовывали одну и ту же концепцию, я использовал векторы вместо массивов C ++ и не включал индексы массивов в аргументы.

Я хотел бы спросить, будет ли моя реализация так же хороша, как стандартная реализация, или я просто должен просто следовать стандартной реализации? Я спрашиваю с точки зрения эффективности, когда размер ввода становится намного больше.

0

Решение

Задача ещё не решена.

Другие решения


По вопросам рекламы ammmcru@yandex.ru
Adblock
detector