fork download
copy 
  1. #include <vector>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <random>
  6. #include <chrono>
  7. #include <limits>
  8.  
  9. class muTimer
  10. {
  11.     using Clock = std::chrono::high_resolution_clock;
  12.     bool active = false;
  13.     Clock::duration   duration_;
  14.     Clock::time_point start_ = Clock::now(), stop_ = Clock::now();
  15.  
  16.     muTimer(const muTimer&)             = delete;
  17.     muTimer& operator=(const muTimer&)  = delete;
  18. public:
  19.     using ns       = std::chrono::nanoseconds;
  20.     using mks      = std::chrono::microseconds;
  21.     using ms       = std::chrono::milliseconds;
  22.     muTimer() { reset(); start(); }
  23.     ~muTimer() = default;
  24.     muTimer& reset()
  25.     {
  26.         duration_ = std::chrono::nanoseconds(0);
  27.         active    = false;
  28.         return *this;
  29.     }
  30.     muTimer& start()
  31.     {
  32.         if (!active)
  33.         {
  34.             start_ = Clock::now();
  35.             active = true;
  36.         }
  37.         return *this;
  38.     }
  39.     muTimer& stop()
  40.     {
  41.         if (active)
  42.         {
  43.             stop_      = Clock::now();
  44.             duration_ += stop_ - start_;
  45.             active     = false;
  46.         }
  47.         return *this;
  48.     }
  49.     template<typename T = mks>
  50.         unsigned long long duration()
  51.     {
  52.         return static_cast<unsigned long long>
  53.             (std::chrono::duration_cast<T>(stop_-start_).count());
  54.     }
  55. };
  56.  
  57. using namespace std;
  58.  
  59.  
  60. // BubbleSort
  61. template<typename Iter>
  62. void BubbleSort(Iter b, Iter e)
  63. {
  64.     --e;
  65.     for(; b != e; ++b)
  66.         for(Iter k = e, j = k--; j != b; j = k--)
  67.             if (*j < *k) swap(*j,*k);
  68. }
  69.  
  70. // EBubbleSort
  71. template<typename Iter>
  72. void EBubbleSort(Iter b, Iter e)
  73. {
  74.     --e;
  75.     for(; b != e; ++b)
  76.     {
  77.         Iter last = e;
  78.         for(Iter k = e, j = k--; j != b; j = k--)
  79.             if (*j < *k)
  80.             {
  81.                 swap(*j,*k);
  82.                 last = k;
  83.             }
  84.         if (last == e) break; else b = last;
  85.     }
  86. }
  87.  
  88. template<typename Iter>
  89. void InsertionSort(Iter b, Iter e)
  90. {
  91.     typedef typename iterator_traits<Iter>::value_type Value;
  92.     Iter i = b;
  93.     for(++i; i != e; ++i)
  94.     {
  95.         Value x = *i;
  96.         Iter j = i, k = i;
  97.         for(--j; (k != b) && (x < *j); --j, --k) *k = *j;
  98.         *k = x;
  99.     }
  100. }
  101.  
  102. template<typename Iter>
  103. void SelectionSort(Iter b, Iter e)
  104. {
  105.     for(; b!= e; ++b)
  106.     {
  107.         Iter mini = b, i = b;
  108.         for(++i; i != e; ++i)
  109.             if (*i < *mini) mini = i;
  110.         if (b != mini) swap(*b,*mini);
  111.     }
  112. }
  113.  
  114.  
  115.  
  116. using matrix = vector<vector<int>>;
  117.  
  118. int main(int argc, char * argv[])
  119. {
  120.     random_device rd;  
  121.     mt19937 gen(rd()); 
  122.     uniform_int_distribution<> dis(numeric_limits<int>::min(), numeric_limits<int>::max());
  123.     const int EXPS = 100000;
  124.  
  125.     for(int N = 4; N <= 32; N *= 2)
  126.     {
  127.         // ‡ Ї®«­пҐ¬
  128.         matrix m;
  129.         for(int i = 0; i < EXPS; ++i)
  130.         {
  131.             vector<int> v;
  132.             for(int j = 0; j < N; ++j) v.push_back(dis(gen));
  133.             m.push_back(v);
  134.         }
  135.         {
  136.             matrix s = m;
  137.             muTimer mt;
  138.             for(auto& v: s) sort(v.begin(),v.end());
  139.             mt.stop();
  140.             long long sum = 0;
  141.             for(const auto& v: m)
  142.                 for(auto i: v) sum += i;
  143.             cout << "stl sort    : N = " << setw(2) << N << " : " <<
  144.                 sum << " for " << setw(6) << mt.duration<>() << " mks\n";
  145.         }
  146.         {
  147.             matrix s = m;
  148.             muTimer mt;
  149.             for(auto& v: s) stable_sort(v.begin(),v.end());
  150.             mt.stop();
  151.             long long sum = 0;
  152.             for(const auto& v: m)
  153.                 for(auto i: v) sum += i;
  154.             cout << "stable sort : N = " << setw(2) << N << " : " <<
  155.                 sum << " for " << setw(6) << mt.duration<>() << " mks\n";
  156.         }
  157.         {
  158.             matrix s = m;
  159.             muTimer mt;
  160.             for(auto& v: s) BubbleSort(v.begin(),v.end());
  161.             mt.stop();
  162.             long long sum = 0;
  163.             for(const auto& v: m)
  164.                 for(auto i: v) sum += i;
  165.             cout << "Bubble sort : N = " << setw(2) << N << " : " <<
  166.                 sum << " for " << setw(6) << mt.duration<>() << " mks\n";
  167.         }
  168.         {
  169.             matrix s = m;
  170.             muTimer mt;
  171.             for(auto& v: s) EBubbleSort(v.begin(),v.end());
  172.             mt.stop();
  173.             long long sum = 0;
  174.             for(const auto& v: m)
  175.                 for(auto i: v) sum += i;
  176.             cout << "EBubble sort: N = " << setw(2) << N << " : " <<
  177.                 sum << " for " << setw(6) << mt.duration<>() << " mks\n";
  178.         }
  179.         {
  180.             matrix s = m;
  181.             muTimer mt;
  182.             for(auto& v: s) InsertionSort(v.begin(),v.end());
  183.             mt.stop();
  184.             long long sum = 0;
  185.             for(const auto& v: m)
  186.                 for(auto i: v) sum += i;
  187.             cout << "Insert sort : N = " << setw(2) << N << " : " <<
  188.                 sum << " for " << setw(6) << mt.duration<>() << " mks\n";
  189.         }
  190.         {
  191.             matrix s = m;
  192.             muTimer mt;
  193.             for(auto& v: s) SelectionSort(v.begin(),v.end());
  194.             mt.stop();
  195.             long long sum = 0;
  196.             for(const auto& v: m)
  197.                 for(auto i: v) sum += i;
  198.             cout << "Select sort : N = " << setw(2) << N << " : " <<
  199.                 sum << " for " << setw(6) << mt.duration<>() << " mks\n";
  200.         }
  201.  
  202.         cout << "\n\n";
  203.     }
  204. }
  205.  
  206.  
Success #stdin #stdout 1.3s 37164KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
stl sort    : N =  4 : -767473439994 for   3193 mks
stable sort : N =  4 : -767473439994 for   7362 mks
Bubble sort : N =  4 : -767473439994 for   2554 mks
EBubble sort: N =  4 : -767473439994 for   2430 mks
Insert sort : N =  4 : -767473439994 for   2311 mks
Select sort : N =  4 : -767473439994 for   2854 mks


stl sort    : N =  8 : -2150567459107 for   7677 mks
stable sort : N =  8 : -2150567459107 for  12265 mks
Bubble sort : N =  8 : -2150567459107 for  10729 mks
EBubble sort: N =  8 : -2150567459107 for   8994 mks
Insert sort : N =  8 : -2150567459107 for   7072 mks
Select sort : N =  8 : -2150567459107 for  10428 mks


stl sort    : N = 16 : 470961947972 for  17756 mks
stable sort : N = 16 : 470961947972 for  30181 mks
Bubble sort : N = 16 : 470961947972 for  51772 mks
EBubble sort: N = 16 : 470961947972 for  42733 mks
Insert sort : N = 16 : 470961947972 for  18574 mks
Select sort : N = 16 : 470961947972 for  39494 mks


stl sort    : N = 32 : 968222918847 for  59258 mks
stable sort : N = 32 : 968222918847 for  73074 mks
Bubble sort : N = 32 : 968222918847 for 181751 mks
EBubble sort: N = 32 : 968222918847 for 161596 mks
Insert sort : N = 32 : 968222918847 for  51070 mks
Select sort : N = 32 : 968222918847 for 154799 mks
https://ideone.com/s2pFfu
language:
C++14 (gcc 8.3)
created:
2 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!