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


stl sort    : N =  8 : 39961621038704 for   5894 mks
stable sort : N =  8 : 39961621038704 for   9441 mks
Bubble sort : N =  8 : 39961621038704 for   8255 mks
EBubble sort: N =  8 : 39961621038704 for   6915 mks
Insert sort : N =  8 : 39961621038704 for   5403 mks
Select sort : N =  8 : 39961621038704 for   8000 mks


stl sort    : N = 16 : 80029551570294 for  13609 mks
stable sort : N = 16 : 80029551570294 for  23086 mks
Bubble sort : N = 16 : 80029551570294 for  38195 mks
EBubble sort: N = 16 : 80029551570294 for  33228 mks
Insert sort : N = 16 : 80029551570294 for  14247 mks
Select sort : N = 16 : 80029551570294 for  30328 mks


stl sort    : N = 32 : 160009733839205 for  50951 mks
stable sort : N = 32 : 160009733839205 for  55821 mks
Bubble sort : N = 32 : 160009733839205 for 140012 mks
EBubble sort: N = 32 : 160009733839205 for 125062 mks
Insert sort : N = 32 : 160009733839205 for  39100 mks
Select sort : N = 32 : 160009733839205 for 119110 mks
https://ideone.com/EduCM3
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!