1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Why the unnecessary extra space? Quicksort sorts in-place. You use 3 extra vectors 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.