Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Quick Sort (recursive)
#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;
}
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.