Quick Sort (recursive)

quicksort_r.cpp

#include <iostream>
#include <vector>

template <class T>
int partition(std::vector<T>& vals, int l, int r) {
    int i=l-1, j=r, v=vals[r];
    for (;;) {
        while (vals[++i] < v) ;
        while (vals[--j] > v) if (j<1) break;
        if (i>=j) break;
        std::swap(vals[i], vals[j]);
    }
    std::swap(vals[i], vals[r]);
    return i;
}

template <class T>
void quicksort(std::vector<T>& vals, int l, int r) {
    if (r-l < 1)
        return;
    int i = partition(vals, l, r);
    quicksort(vals, l, i-1);
    quicksort(vals, i+1, r);
}

template <class T>
void quicksort(std::vector<T>& vals) {
    quicksort(vals, 0, vals.size()-1);
}

template <class T>
void print_v(const std::vector<T>& vals) {
    for (auto val : vals)
        std::cout << val << " ";
    std::cout << std::endl;
}

int main()
{
    std::vector<int> nums { 5,2,8,1,4,3,7,6 };
    print_v(nums);
    quicksort(nums);
    print_v(nums);

    return 0;
}