fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. std::vector<int> quick_sort(const std::vector<int> &data)
  8. {
  9. 	if (data.empty())
  10. 		return std::vector<int>();
  11.  
  12. 	std::vector<int> left;
  13. 	left.reserve(data.size());
  14. 	std::vector<int> right;
  15. 	right.reserve(data.size());
  16. 	int x = data[0];
  17.  
  18. 	std::partition_copy(data.begin() + 1, data.end(), std::back_inserter(left), std::back_inserter(right), [x](int y){return y < x;});
  19.  
  20. 	std::vector<int> result;
  21. 	auto sl = quick_sort(left);
  22. 	auto sr = quick_sort(right);
  23. 	result.insert(result.end(), sl.begin(), sl.end());
  24. 	result.push_back(x);
  25. 	result.insert(result.end(), sr.begin(), sr.end());
  26. 	return result;
  27. }
  28.  
  29. std::vector<int> quick_sort(const std::initializer_list<int> &in)
  30. {
  31. 	std::vector<int> data(in);
  32. 	return quick_sort(data);
  33. }
  34.  
  35. int main() {
  36.  
  37. 	auto res = quick_sort({10, 9, 7, 8, 5, 6, 4, 7, 2, 1});
  38. 	for (int i : res)
  39. 		std::cout << i << ' ';
  40.  
  41. 	std::cout << endl;
  42.  
  43. 	return 0;
  44. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 4 5 6 7 7 8 9 10
https://ideone.com/yTIuEQ
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!