fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #include <chrono>
  4. using namespace std::chrono;
  5. #define ll long long int
  6. #define ull unsigned ll
  7. #define yes cout<<"YES"<<endl;
  8. #define no cout<<"NO"<<endl;
  9. #define pb push_back
  10. #define vll vector<ll>
  11. #define vp vector<pair<ll, ll>>
  12. #define all(v) v.begin(), v.end()
  13. #define hcf(a,b) __gcd(a,b)
  14. #define lcm(a,b) (a*b)/hcf(a,b)
  15. #define fori(n) for (ll i = 0; i < n; ++i)
  16. #define forj(n) for (ll j = 0; j < n; ++j)
  17. #define fork(n) for (ll k = 0; k < n; ++k)
  18. bool isPrime (ll a) { if (a < 2) return false; for (ll i = 2; i * i <= a; i++) if (a % i == 0) return false; return true; }
  19. const int M = 1e9 + 7;
  20.  
  21. void bubble_sort(vll &v) {
  22.     int n = v.size();
  23.     fori(n - 1) {
  24.         forj (n-i-1) {
  25.             if (v[j]>v[j+1]) swap(v[j], v[j + 1]);
  26.         }
  27.     }
  28. }
  29.  
  30. vll generate_case(int n, string type) {
  31.     vll v(n);
  32.     if (type == "best") {
  33.         iota(v.begin(), v.end(), 1); 
  34.     } else if (type == "worst") {
  35.         iota(v.begin(), v.end(), 1);
  36.         reverse(v.begin(), v.end()); 
  37.     } else {
  38.         fori(n) v[i] = rand() % (10 * n); 
  39.     }
  40.     return v;
  41. }
  42.  
  43. int main() {
  44.     srand(time(0));
  45.     ofstream fout("bubble_data.dat");
  46.     fout << "#Size Best(ms) Average(ms) Worst(ms)\n";
  47.  
  48.     for (int size = 100; size <= 2000; size += 200) {
  49.         cout << "Running size: " << size << endl;
  50.         fout << size << " ";
  51.  
  52.         for (string type : {"best", "avg", "worst"}) {
  53.             vll v = generate_case(size, type);
  54.             auto start = high_resolution_clock::now();
  55.             bubble_sort(v);
  56.             auto end = high_resolution_clock::now();
  57.             auto duration = duration_cast<microseconds>(end - start).count();
  58.             fout << duration / 1000.0 << " ";
  59.         }
  60.         fout << "\n";
  61.     }
  62.  
  63.     fout.close();
  64.  
  65.     // Write gnuplot script
  66.     ofstream gp("plot_script.gp");
  67.     gp << "set title 'Bubble Sort: Input Size vs Time'\n";
  68.     gp << "set xlabel 'Input Size (n)'\n";
  69.     gp << "set ylabel 'Time (ms)'\n";
  70.     gp << "set grid\n";
  71.     gp << "set key left top\n";
  72.     gp << "plot 'bubble_data.dat' using 1:2 with linespoints title 'Best', \\\n";
  73.     gp << "     'bubble_data.dat' using 1:3 with linespoints title 'Average', \\\n";
  74.     gp << "     'bubble_data.dat' using 1:4 with linespoints title 'Worst'\n";
  75.     gp.close();
  76.  
  77.     // Run gnuplot
  78.     system("gnuplot -persist plot_script.gp");
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout #stderr 0.03s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Running size: 100
Running size: 300
Running size: 500
Running size: 700
Running size: 900
Running size: 1100
Running size: 1300
Running size: 1500
Running size: 1700
Running size: 1900
stderr
copy 
sh: 1: gnuplot: not found
https://ideone.com/b5IqGM
language:
C++ (gcc 8.3)
created:
6 days 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!