Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Quick Sort (iterative)
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.