Quick Sort (iterative)

quicksort_i.cpp

#include <iostream>
#include <vector>
#include <stack>

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) {
    std::stack<std::pair<int,int>> s;
    s.push({l,r});

    while (s.size() > 0) {	
        auto bounds = s.top();
        s.pop();
        int cur_l = bounds.first;
        int cur_r = bounds.second;
        if (cur_r-cur_l >= 1) {
            int i = partition(vals, cur_l, cur_r);
            s.push({cur_l,i-1});
            s.push({i+1,cur_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;
}