Skip to content

Instantly share code, notes, and snippets.

# adamkorg/quicksort_i.cpp Created Mar 30, 2019

Quick Sort (iterative)
 #include #include #include template int partition(std::vector& 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 void quicksort(std::vector& vals, int l, int r) { std::stack> 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 void quicksort(std::vector& vals) { quicksort(vals, 0, vals.size()-1); } template void print_v(const std::vector& vals) { for (auto val : vals) std::cout << val << " "; std::cout << std::endl; } int main() { std::vector nums { 5,2,8,1,4,3,7,6 }; print_v(nums); quicksort(nums); print_v(nums); return 0; }
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.