fork download
copy 
  1. #include <vector>
  2. #include <string>
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <chrono>
  6. #include <random>
  7. #include <algorithm>
  8.  
  9. using namespace std;
  10.  
  11. class muTimer
  12. {
  13.     using Clock = std::chrono::high_resolution_clock;
  14.     bool active = false;
  15.     Clock::duration   duration_;
  16.     Clock::time_point start_ = Clock::now(), stop_ = Clock::now();
  17.  
  18.     muTimer(const muTimer&)             = delete;
  19.     muTimer& operator=(const muTimer&)  = delete;
  20. public:
  21.     using ns       = std::chrono::nanoseconds;
  22.     using mks      = std::chrono::microseconds;
  23.     using ms       = std::chrono::milliseconds;
  24.     muTimer() { reset(); start(); }
  25.     ~muTimer() = default;
  26.     muTimer& reset()
  27.     {
  28.         duration_ = std::chrono::nanoseconds(0);
  29.         active    = false;
  30.         return *this;
  31.     }
  32.     muTimer& start()
  33.     {
  34.         if (!active)
  35.         {
  36.             start_ = Clock::now();
  37.             active = true;
  38.         }
  39.         return *this;
  40.     }
  41.     muTimer& stop()
  42.     {
  43.         if (active)
  44.         {
  45.             stop_      = Clock::now();
  46.             duration_ += stop_ - start_;
  47.             active     = false;
  48.         }
  49.         return *this;
  50.     }
  51.     template<typename T = mks>
  52.         unsigned long long duration()
  53.     {
  54.         return static_cast<unsigned long long>
  55.             (std::chrono::duration_cast<T>(stop_-start_).count());
  56.     }
  57. };
  58.  
  59.  
  60. template< class T >
  61. unsigned long bubbleSort(T* arr, int size)
  62. {
  63.  
  64.     unsigned long swaps = 0;
  65.     T tmp;
  66.  
  67.     for(int i = 0; i < size - 1; ++i) // i - номер прохода
  68.     {            
  69.         for(int j = 0; j < size - 1; ++j) // внутренний цикл прохода
  70.         {     
  71.             if (arr[j + 1] < arr[j]) 
  72.             {
  73.                 tmp = arr[j + 1]; 
  74.                 arr[j + 1] = arr[j]; 
  75.                 arr[j] = tmp;
  76.                 ++swaps;
  77.             }
  78.         }
  79.     }
  80.     return swaps;
  81. }
  82.  
  83.  
  84. int main(int argc, const char * argv[])
  85. {
  86.     vector<int> ave;
  87.     vector<int> bad;
  88.  
  89.     const int Count = 20000;
  90.  
  91.     for(int i = 0; i < Count; ++i)
  92.     {
  93.         bad.push_back(Count-i);
  94.     }
  95.  
  96.     std::random_device rd;
  97.     std::mt19937 g(rd());
  98.  
  99.     ave = bad;
  100.     shuffle(ave.begin(),ave.end(),g);
  101.  
  102.     {
  103.         muTimer mu;
  104.         unsigned long sw = bubbleSort(ave.data(),ave.size());
  105.         mu.stop();
  106.         cout << "Ave: " << mu.duration<muTimer::ms>() << " ms, swaps: " << sw << endl;
  107.     }
  108.     {
  109.         muTimer mu;
  110.         unsigned long sw = bubbleSort(bad.data(),bad.size());
  111.         mu.stop();
  112.         cout << "Bad: " << mu.duration<muTimer::ms>() << " ms, swaps: " << sw << endl;
  113.     }
  114.  
  115. }
  116.  
  117.  
  118.  
Success #stdin #stdout 0.98s 4308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Ave: 607 ms, swaps: 100274594
Bad: 362 ms, swaps: 199990000
https://ideone.com/KHUS7T
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!