I tried to make a simple qsort() function in a functional way, it takes a vector and a bool pred()
Suggestions as to make it more functional, optimize it, and/or remove extra steps and intermediate variables are appreciated
template <typename T>
void operator+=(std::vector<T> &v1, const std::vector<T> &v2) {
v1.insert(v1.end(), v2.begin(), v2.end());
}
template <typename T, typename Func>
std::vector<T> qsort(const std::vector<T>& in, const Func& pred) {
std::vector<T> out;
std::vector<T> less;
std::vector<T> more;
if (in.size() < 2)
return in;
auto p = in[0];
for (auto i = 1; i < in.size(); i++) {
if (pred(p, in[i]))
less.push_back(in[i]);
else
more.push_back(in[i]);
}
out = qsort(less, pred);
out.push_back(p);
out += qsort(more, pred);
return out;
}
vector
s in the function. Each one of these results in a dynamic memory allocation, which will adversely affect the performance of your implementation. \$\endgroup\$ – Mike Borkland Nov 20 '18 at 16:26