#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <chrono>
#include <random>
#include <algorithm>
using namespace std;
class muTimer
{
using Clock = std::chrono::high_resolution_clock;
bool active = false;
Clock::duration duration_;
Clock::time_point start_ = Clock::now(), stop_ = Clock::now();
muTimer(const muTimer&) = delete;
muTimer& operator=(const muTimer&) = delete;
public:
using ns = std::chrono::nanoseconds;
using mks = std::chrono::microseconds;
using ms = std::chrono::milliseconds;
muTimer() { reset(); start(); }
~muTimer() = default;
muTimer& reset()
{
duration_ = std::chrono::nanoseconds(0);
active = false;
return *this;
}
muTimer& start()
{
if (!active)
{
start_ = Clock::now();
active = true;
}
return *this;
}
muTimer& stop()
{
if (active)
{
stop_ = Clock::now();
duration_ += stop_ - start_;
active = false;
}
return *this;
}
template<typename T = mks>
unsigned long long duration()
{
return static_cast<unsigned long long>
(std::chrono::duration_cast<T>(stop_-start_).count());
}
};
template< class T >
unsigned long bubbleSort(T* arr, int size)
{
unsigned long swaps = 0;
T tmp;
for(int i = 0; i < size - 1; ++i) // i - номер прохода
{
for(int j = 0; j < size - 1; ++j) // внутренний цикл прохода
{
if (arr[j + 1] < arr[j])
{
tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
++swaps;
}
}
}
return swaps;
}
int main(int argc, const char * argv[])
{
vector<int> ave;
vector<int> bad;
const int Count = 20000;
for(int i = 0; i < Count; ++i)
{
bad.push_back(Count-i);
}
std::random_device rd;
std::mt19937 g(rd());
ave = bad;
shuffle(ave.begin(),ave.end(),g);
{
muTimer mu;
unsigned long sw = bubbleSort(ave.data(),ave.size());
mu.stop();
cout << "Ave: " << mu.duration<muTimer::ms>() << " ms, swaps: " << sw << endl;
}
{
muTimer mu;
unsigned long sw = bubbleSort(bad.data(),bad.size());
mu.stop();
cout << "Bad: " << mu.duration<muTimer::ms>() << " ms, swaps: " << sw << endl;
}
}