fork download 
  1. // Quicksort using Djikstra's 3-way partition.
  2.  
  3. #include <functional>
  4. #include <algorithm>
  5. #include <random>
  6. #include <chrono>
  7. #include <iostream>
  8. using namespace std;
  9.  
  10. int randint(int a, int b)
  11. {
  12.     thread_local default_random_engine re(random_device{}());
  13.     uniform_int_distribution<> pick(a, b);
  14.     return pick(re);
  15. }
  16.  
  17. void timeit(function<void()> thunk)
  18. {
  19.     using clock = chrono::steady_clock;
  20.     clock::time_point t = clock::now();
  21.     thunk();
  22.     chrono::duration<double> elapsed = clock::now() - t;
  23.     cout << "Elapsed: " << fixed << elapsed.count() << "s\n";
  24. }
  25.  
  26. template<typename In>
  27. ostream& ostream_join(ostream& os, In first, In last, string sep)
  28. {
  29.     if (first != last)
  30.     {
  31.         for (;;)
  32.         {
  33.             os << *first;
  34.             if (++first == last) break;
  35.             os << sep;
  36.         }
  37.     }
  38.     return os;
  39. }
  40.  
  41. template<typename T>
  42. ostream& operator<<(ostream& os, const vector<T>& a)
  43. {
  44.     os << '[';
  45.     ostream_join(os, a.begin(), a.end(), ", ");
  46.     os << ']';
  47.     return os;
  48. }
  49.  
  50. // Sort.
  51.  
  52. template<typename Bi, typename Compare, typename T>
  53. pair<Bi, Bi> partition3(Bi first, Bi last, Compare comp, T pivot)
  54. {
  55.     for (Bi i = first; i != last;)
  56.     {
  57.         if (comp(*i, pivot))
  58.         {
  59.             iter_swap(first++, i++);
  60.         }
  61.         else if (comp(pivot, *i))
  62.         {
  63.             iter_swap(i, --last);
  64.         }
  65.         else
  66.         {
  67.             i++;
  68.         }
  69.     }
  70.     return {first, last};
  71. }
  72.  
  73. template<typename Ran, typename Compare>
  74. void quicksort(Ran first, Ran last, Compare comp)
  75. {
  76.     if (auto n = distance(first, last); n >= 2)
  77.     {
  78.         auto eq = partition3(first, last, comp, *next(first, randint(0, n-1)));
  79.         quicksort(first, eq.first, comp);
  80.         quicksort(eq.second, last, comp);
  81.     }
  82. }
  83.  
  84. template<typename Ran>
  85. void quicksort(Ran first, Ran last)
  86. {
  87.     quicksort(first, last, less<typename iterator_traits<Ran>::value_type>());
  88. }
  89.  
  90. // Main.
  91.  
  92. void test1(int n)
  93. {
  94.     vector<int> t(n);
  95.     generate(t.begin(), t.end(), bind(randint, 1-n, n-1));
  96.     vector<int> u = t;
  97.     sort(u.begin(), u.end());
  98.     vector<int> v = t;
  99.     quicksort(v.begin(), v.end());
  100.     if (u == v)
  101.     {
  102.         cout << "Pass: " << n << endl;
  103.     }
  104.     else
  105.     {
  106.         cout << "Fail: " << n << endl;
  107.         for (auto x : {t, u, v})
  108.             cout << x << endl;
  109.     }
  110. }
  111.  
  112. void time1(int n)
  113. {
  114.     vector<int> t(n);
  115.     generate(t.begin(), t.end(), bind(randint, 1-n, n-1));
  116.     timeit([&]{
  117.         quicksort(t.begin(), t.end());
  118.     });
  119. }
  120.  
  121. void p2call(int j, int k, function<void(int)> f)
  122. {
  123.     int m = 1;
  124.     for (int i = 0; i < j; i++)
  125.         m *= 2;
  126.     for (int i = j; i < k; i++)
  127.     {
  128.         f(m-1);
  129.         m *= 2;
  130.     }
  131. }
  132.  
  133. int main()
  134. {
  135.     p2call(0, 6, test1);
  136.     p2call(16, 22, time1);
  137. }
Success #stdin #stdout 0.53s 11504KB
comments (?)
stdin 
Standard input is empty
stdout 
Pass: 0
Pass: 1
Pass: 3
Pass: 7
Pass: 15
Pass: 31
Elapsed: 0.006098s
Elapsed: 0.012185s
Elapsed: 0.021623s
Elapsed: 0.044014s
Elapsed: 0.116021s
Elapsed: 0.222897s
https://ideone.com/cZqszY
language:
C++ (gcc 8.3)
created:
10 days 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!