Skip to content

Instantly share code, notes, and snippets.

@lfsmoura
Created September 15, 2021 16:18
Show Gist options
  • Save lfsmoura/376938dfa1ca4a568971683e4067372b to your computer and use it in GitHub Desktop.
Save lfsmoura/376938dfa1ca4a568971683e4067372b to your computer and use it in GitHub Desktop.
Quicksort in C++ three lines
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void q(std::vector<int>::iterator b, std::vector<int>::iterator e) {
auto d = std::partition(b, e, [&](int s) { return s <= *b; });
if (b < e) q(b, d - 1), q(d, e);
}
void q2(std::vector<int>::iterator b, std::vector<int>::iterator e) {
if (b >= e) { return; }
std::vector<int> temp, temp2, temp3 { *b };
std::copy_if(b + 1, e, std::back_inserter(temp), [&](int s) { return s < *b; });
q(temp.begin(), temp.end());
std::copy_if(b + 1, e, std::back_inserter(temp2), [&](int s) { return s >= *b; });
q(temp2.begin(), temp2.end());
std::copy(temp2.begin(), temp2.end(), std::copy(temp3.begin(), temp3.end(), std::copy(temp.begin(), temp.end(), b)));
}
int main()
{
std::vector<int> x { 1, 3, 2, 5, 9, 1 };
q(x.begin(), x.end());
for (auto a: x) {
std::cout << a << " - ";
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment