fork download
copy 
  1. // Copyright Evgeny Panasyuk 2013.
  2. // Distributed under the Boost Software License, Version 1.0.
  3. // (See accompanying file LICENSE_1_0.txt or copy at
  4. // http://w...content-available-to-author-only...t.org/LICENSE_1_0.txt)
  5.  
  6. #include <functional>
  7. #include <algorithm>
  8. #include <stdexcept>
  9. #include <iterator>
  10. #include <iostream>
  11. #include <cassert>
  12. #include <cstddef>
  13. #include <string>
  14. #include <vector>
  15.  
  16. using namespace std;
  17.  
  18. template<typename Iterator>
  19. using ValueType = typename iterator_traits<Iterator>::value_type;
  20.  
  21. template<typename I, typename P = less<ValueType<I>>>
  22. /*
  23. requires
  24. (
  25.     ForwardIterator(I) && Mutable(I) &&
  26.     StrictWeakOrdering(P) && Domain(P) == ValueType(I)
  27. )
  28. */
  29. void quick_sort(I first, I last, P p = P())
  30. {
  31.     while(first != last)
  32.     {
  33.         // naive version
  34.         auto pivot = *first;
  35.         auto first_not_less = partition(first, last, bind2nd(p, pivot));
  36.         quick_sort(first, first_not_less, p);
  37.         first = partition(first_not_less, last, not1(bind1st(p, pivot)));
  38.     }
  39. }
  40.  
  41. /************************************************************************/
  42.  
  43. // Generates sorted sequences of given size isomorphic under ordering relation
  44. //    to all other sorted sequences of that size.
  45. // Note, for integer sortings, distance between numbers would also make difference,
  46. //   not just "order".
  47. template<typename I, typename T, typename F>
  48. /*
  49. requires
  50. (
  51.     ForwardIterator(I) && Mutable(I) &&
  52.     Integer(T) && ValueType(I) == T && 
  53.     NullaryFunction(F)
  54. )
  55. */
  56. void generate_sorted_sequences(I first, I last, T x, F yield)
  57. {
  58.     /*
  59.         For n=3 generates:
  60.         0 1 2
  61.         0 1 1
  62.         0 0 1
  63.         0 0 0
  64.     */
  65.     if(first == last) yield();
  66.     else do
  67.     {
  68.         *first = x;
  69.         ++first;
  70.         generate_sorted_sequences(first, last, x + 1, yield);
  71.     } while(first != last);
  72. }
  73.  
  74.  
  75. template<typename I1, typename I2, typename N>
  76. /*
  77. requires
  78. (
  79.     ForwardIterator(I1) && InputIterator(I2) &&
  80.     ValueType(I1) == ValueType(I2) &&
  81.     EqualityComparable( ValueType(I1) ) &&
  82.     Integer(N)
  83. )
  84. */
  85. void require_equal(I1 first1, I1 last1, I2 first2, N n)
  86. {
  87.     if(equal(first1, last1, first2)) return;
  88.  
  89.     cout << "sequence #" << n << ", postcondition does not hold: ";
  90.     copy(first1, last1, ostream_iterator<int>(cout, " "));
  91.     cout << endl;
  92.     throw logic_error("fix the code");
  93. }
  94.  
  95. template<typename T, typename F>
  96. /*
  97.     Regular(T) && SortFunction(F)
  98. */
  99. void test_sort(unsigned N, F sort)
  100. {
  101.     vector<T> v(N), permutation, tmp;
  102.     size_t total = 0;
  103.     for(auto first=begin(v), last=first; last!=end(v); ++last)
  104.     {
  105.         generate_sorted_sequences(first, last, T{}, [&]
  106.         {
  107.             assert(is_sorted(first, last));
  108.             permutation.assign(first, last);
  109.             do
  110.             {
  111.                 tmp = permutation;
  112.                 sort(begin(tmp), end(tmp));
  113.                 require_equal(begin(tmp), end(tmp), first, total);
  114.                 ++total;
  115.             } while(next_permutation(begin(permutation), end(permutation)));
  116.         });
  117.         cout << "tested " << total << " sequences" << endl;
  118.     }
  119. }
  120.  
  121. /************************************************************************/
  122. struct QuickSort
  123. {
  124.     const string name = "Quicksort";
  125.     template<typename I>
  126.     void operator()(I first, I last) const
  127.     {
  128.         quick_sort(first, last);
  129.     }
  130. };
  131. struct StdSort
  132. {
  133.     const string name = "std::sort";
  134.     template<typename I>
  135.     void operator()(I first, I last) const
  136.     {
  137.         sort(first, last);
  138.     }
  139. };
  140. struct StdStableSort
  141. {
  142.     const string name = "std::stable_sort";
  143.     template<typename I>
  144.     void operator()(I first, I last) const
  145.     {
  146.         stable_sort(first, last);
  147.     }
  148. };
  149. struct StdParialSort
  150. {
  151.     const string name = "std::partial_sort";
  152.     template<typename I>
  153.     void operator()(I first, I last) const
  154.     {
  155.         partial_sort(first, last, last);
  156.     }
  157. };
  158.  
  159. /************************************************************************/
  160.  
  161. template<typename SortFunction>
  162. void test()
  163. {
  164.     SortFunction f;
  165.     cout << "Testing " << f.name << endl;
  166.     test_sort<int>(10, f);
  167.     cout << string(32, '_') << endl;
  168. }
  169.  
  170. template<typename SortFunction, typename Head, typename ...Tail>
  171. void test()
  172. {
  173.     test<SortFunction>();
  174.     test<Head, Tail...>();
  175. }
  176.  
  177. int main()
  178. {
  179.     test<QuickSort, StdSort, StdStableSort, StdParialSort>();
  180. }
  181.  
Success #stdin #stdout 7.89s 3004KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Testing Quicksort
tested 1 sequences
tested 2 sequences
tested 5 sequences
tested 18 sequences
tested 93 sequences
tested 634 sequences
tested 5317 sequences
tested 52610 sequences
tested 598445 sequences
tested 7685706 sequences
________________________________
Testing std::sort
tested 1 sequences
tested 2 sequences
tested 5 sequences
tested 18 sequences
tested 93 sequences
tested 634 sequences
tested 5317 sequences
tested 52610 sequences
tested 598445 sequences
tested 7685706 sequences
________________________________
Testing std::stable_sort
tested 1 sequences
tested 2 sequences
tested 5 sequences
tested 18 sequences
tested 93 sequences
tested 634 sequences
tested 5317 sequences
tested 52610 sequences
tested 598445 sequences
tested 7685706 sequences
________________________________
Testing std::partial_sort
tested 1 sequences
tested 2 sequences
tested 5 sequences
tested 18 sequences
tested 93 sequences
tested 634 sequences
tested 5317 sequences
tested 52610 sequences
tested 598445 sequences
tested 7685706 sequences
________________________________
https://ideone.com/WeZU66
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
secret

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!