'MergeSort C++ using vectors
I have been trying to fix my code for a while now, and while it does print out the numbers, it only prints them out in the order that I gave them in. It's not really doing the merge sort as it was intended to, don't know if I missed typed something but would really appreciate the feedback and help. Also the part where it says static void ordena(typename std::vector<T>::iterator &&b, typename std::vector<T>::iterator &&e) that can't be changed whatsoever since it's required for me to have it to turn it in.
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
template<typename T>
class mergeSort {
public:
static void ordena(typename std::vector<T>::iterator &&b, typename std::vector<T>::iterator &&e) {
if (b-e+1 <= 1)
return;
auto iter = b + (b-e+1) / 2;
vector<T> v1(b, iter);
vector<T> v2(iter, e);
ordena(v1.begin(),v1.end());
ordena(v2.begin(),v2.end());
vector<T> v3;
merge(v3, v1, v2);
}
static void merge(vector<T> &v3, 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))
v3.push_back(v1.at(p1++));
else
v3.push_back(v2.at(p2++));
}
while (p1 < siz1) v3.push_back(v1.at(p1++));
while (p2 < siz2) v3.push_back(v2.at(p2++));
}
};
template<typename T>
std::string to_string(const std::vector<T> &elements){
std::string str{};
for(T e : elements) str += std::to_string(e) + ", ";
return str.substr(0,str.length()-2);
}
int main()
{
vector<int> elements;
elements.push_back(100);
elements.push_back(10);
elements.push_back(80);
elements.push_back(30);
elements.push_back(60);
elements.push_back(50);
elements.push_back(40);
elements.push_back(70);
elements.push_back(20);
elements.push_back(90);
mergeSort<int>::ordena(elements.begin(), elements.end());
std::cout << "First ordered sequence : " << to_string(elements) << std::endl;
}
Solution 1:[1]
After merge(v3, v1, v2), copy v3 to *b to *(e-1). This is not an efficient way to do this, but it should work.
// only single reference is needed
static void ordena(typename std::vector<T>::iterator &b, typename std::vector<T>::iterator &e) {
// ...
merge(v3, v1, v2);
std::copy(v3.begin(), v3.end(), b);
You could also change merge to take an iterator as the first parameter
merge(b, v1, v2);
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | rcgldr |
