fork download
copy 
  1. #include <vector>
  2. #include <algorithm>
  3. #include <iterator>
  4. #include <iostream>
  5. #include <functional>
  6.  
  7. // iterator check
  8. template <typename It, typename T>
  9. constexpr bool is = std::is_same<typename std::iterator_traits<It>::iterator_category, T>::value;
  10.  
  11.  
  12. // quick sort
  13. template <typename BidIt, typename Pred = typename std::less<typename std::iterator_traits<BidIt>::value_type>>
  14. void qsort(BidIt first, BidIt last, Pred compare = {}) noexcept
  15. {
  16.     static_assert(is<BidIt, std::bidirectional_iterator_tag> || is<BidIt, std::random_access_iterator_tag>,
  17.         "at least bidirectional iterator required");
  18.  
  19.     auto size = std::distance(first, last);
  20.  
  21.     if (size > 1) {
  22.         using content_type = typename std::iterator_traits<BidIt>::value_type;
  23.  
  24.         content_type pivot = *first;
  25.         std::vector<content_type> left, right;
  26. 		left.reserve(size);
  27. 		right.reserve(size);
  28.         auto left_end = std::back_inserter(left);
  29.         auto right_end = std::back_inserter(right);
  30.  
  31.         for (BidIt i = std::next(first); i != last; ++i) {
  32.             compare(*i, pivot) ? *left_end++ = *i : *right_end++ = *i;
  33.         }
  34.  
  35.         qsort(left.begin(), left.end(), compare);
  36.         qsort(right.begin(), right.end(), compare);
  37.  
  38.         std::copy(left.begin(), left.end(), first);
  39.         *std::next(first, std::distance(left.begin(), left.end())) = pivot;
  40.         std::copy(right.begin(), right.end(), std::next(first, std::distance(left.begin(), left.end()) + 1));
  41.     }
  42. }
  43.  
  44. struct integer
  45. {
  46. 	integer() = delete; //not default constructible
  47. 	integer(int y):
  48. 				x(y)
  49. 	{}
  50.  
  51. 	int x;
  52. };
  53.  
  54. bool operator<(const integer& lhs, const integer& rhs)
  55. {
  56. 	return lhs.x < rhs.x;
  57. }
  58.  
  59. std::ostream& operator<<(std::ostream& os, const integer& x)
  60. {
  61. 	os << x.x;
  62. 	return os;
  63. }
  64.  
  65. int main() {
  66. 	std::vector<integer> v{1, 0, -1, 4, 2};
  67. 	qsort(v.begin(), v.end());
  68. 	std::copy(v.begin(), v.end(), std::ostream_iterator<integer>(std::cout, " "));
  69. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1 0 1 2 4
https://ideone.com/anlLdB
language:
C++14 (gcc 8.3)
created:
6 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!