rewrite the merge sort algorithm as a template function. Use two template parame
ID: 3550070 • Letter: R
Question
rewrite the merge sort algorithm as a template function. Use two template parameters, one to set the element type, and the second todefine the ordering algorithm
#include <iostream>
#include "util.h"
void merge(vector<int>& a, int from, int mid, int to)
{
int n = to - from + 1;
vector<int> b(n);
int i1 = from;
int i2 = mid + 1;
int j = 0;
while(i1 <= mid && i2 <= to)
{
if (a[i1] < a[i2])
{
b[j] = a[i1];
i1++;
}
else
{
b[j] = a[i2];
i2++;
}
j++
}
while(i1 <= mid)
{
b[j] = a[i1];
i1++;
j++;
}
while(i2 <= to)
{
b[j] = a[i2];
i2++;
j++;
}
for(j = 0; j < n; j++)
a[from + j] = b[j];
}
void merge_sort(vector<int>& a, int from, int to)
{
if(from == to) return;
int mid = (from + to) / 2;
merge_sort(a, from, mid);
merge_sort(a, mid + 1, to);
merge(a, from, mid, to);
}
int main()
{
rand_seed();
vector<int> v(20);
for(int i = 0; i < v.size(); i++)
v[i] = rand_int(1, 100);
print(v);
merge_sort(v, 0, v.size() - 1);
print(v);
return 0;
}
Explanation / Answer
#include
<iostream>
#include
<vector>
#include
<cstdlib>
#include
<ctime>
using
namespace std;
template
<class T>
void
merge(T& a, int from, int mid, int to)
{
int n = to - from + 1;
T b(n);
int i1 = from;
int i2 = mid + 1;
int j = 0;
while(i1 <= mid && i2 <= to)
{
if (a[i1] < a[i2])
{
b[j] = a[i1];
i1++;
}
else
{
b[j] = a[i2];
i2++;
}
j++;
}
while(i1 <= mid)
{
b[j] = a[i1];
i1++;
j++;
}
while(i2 <= to)
{
b[j] = a[i2];
i2++;
j++;
}
for(j = 0; j < n; j++)
a[from + j] = b[j];
}
template
<class T>
void
merge_sort(T& a, int from, int to)
{
if(from == to)
return;
int mid = (from + to) / 2;
merge_sort(a, from, mid);
merge_sort(a, mid + 1, to);
merge(a, from, mid, to);
}
template
<class T>
void
print(T& a)
{
for(int i = 0; i < a.size(); i++)
cout << a[i] <<
" ";
cout << endl;
}
int
main()
{
srand(time(NULL));
vector<
int> v(20);
for(int i = 0; i < v.size(); i++)
v[i] = 1 + rand() % 100;
?
?
print(v);
merge_sort(v, 0, v.size() - 1);
print(v);
vector<
double> v2;
v2.push_back(2.5);
v2.push_back(1.9);
v2.push_back(3.9);
v2.push_back(4.1);
v2.push_back(2.5);
print(v2);
merge_sort(v2, 0, v2.size() - 1);
print(v2);
system(
"pause");
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.