Ideone.com

fork download

copy

#include "cmath"
#include <chrono>
#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstdlib>
 
using namespace std::chrono;
 
int RandomNumber2() { return (std::rand() % 100); }
void FillVector(std::vector<int>& a) {
    std::srand(unsigned(std::time(0)));
    std::generate(a.begin(), a.end(), RandomNumber2);
    std::cout << "\n\nVector: ";
    for (std::vector<int>::iterator it = a.begin(); it != a.end(); it++) std::cout << *it << " ";
}
 
void CocktailSort(std::vector<int>& a, int n) {
	   bool flag = true;
   int start = 0, end = n-1;
   while(flag){
      flag = false;
      for(int i = start; i<end; i++){
         if(a[i] > a[i+1]){
            std::swap(a[i], a[i+1]);
            flag = true;
         }
      }
      if(!flag){
         break;
      }
      flag = false;
      end--;
      for(int i = end - 1; i >= start; i--){
         if(a[i] > a[i+1]){
            std::swap(a[i], a[i+1]);
            flag = true;
         }
      }
      start++;
   }
}
 
double measureTime(std::vector<int>& a, int n) {
    steady_clock::time_point t1 = steady_clock::now();
    CocktailSort(a, n);
    steady_clock::time_point t2 = steady_clock::now();
    duration<double> time_span = duration_cast<duration<double>>(t2 - t1);
    double mTime = time_span.count();
    std::cout <<  mTime << std::endl;
    return mTime;
}
 
 
void Experiment(std::vector<int> &a, int n) {
    FillVector(a);
    CocktailSort(a, n);
    std::cout << "\n\na. Sorted data: ";
    for (int i{ 0 }; i < n; i++) std::cout << a[i] <<  ' ';
 
    double* times = new double[1000];
 
    for (int i=100; i < 1000; i += 100) {
        std::cout << "\n[" << i << "]" << " ";
        for (int j{1}; j < 10; j+=1) {
            times[j] = measureTime(a, i);
        }
    }
}
 
int main() {
    int n{1000};
    std::vector<int> a(n);
    Experiment(a, n);
 
    return 0;
}

I2luY2x1ZGUgImNtYXRoIgojaW5jbHVkZSA8Y2hyb25vPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxjdGltZT4KI2luY2x1ZGUgPGNzdGRsaWI+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOjpjaHJvbm87CgppbnQgUmFuZG9tTnVtYmVyMigpIHsgcmV0dXJuIChzdGQ6OnJhbmQoKSAlIDEwMCk7IH0Kdm9pZCBGaWxsVmVjdG9yKHN0ZDo6dmVjdG9yPGludD4mIGEpIHsKICAgIHN0ZDo6c3JhbmQodW5zaWduZWQoc3RkOjp0aW1lKDApKSk7CiAgICBzdGQ6OmdlbmVyYXRlKGEuYmVnaW4oKSwgYS5lbmQoKSwgUmFuZG9tTnVtYmVyMik7CiAgICBzdGQ6OmNvdXQgPDwgIlxuXG5WZWN0b3I6ICI7CiAgICBmb3IgKHN0ZDo6dmVjdG9yPGludD46Oml0ZXJhdG9yIGl0ID0gYS5iZWdpbigpOyBpdCAhPSBhLmVuZCgpOyBpdCsrKSBzdGQ6OmNvdXQgPDwgKml0IDw8ICIgIjsKfQoKdm9pZCBDb2NrdGFpbFNvcnQoc3RkOjp2ZWN0b3I8aW50PiYgYSwgaW50IG4pIHsKCSAgIGJvb2wgZmxhZyA9IHRydWU7CiAgIGludCBzdGFydCA9IDAsIGVuZCA9IG4tMTsKICAgd2hpbGUoZmxhZyl7CiAgICAgIGZsYWcgPSBmYWxzZTsKICAgICAgZm9yKGludCBpID0gc3RhcnQ7IGk8ZW5kOyBpKyspewogICAgICAgICBpZihhW2ldID4gYVtpKzFdKXsKICAgICAgICAgICAgc3RkOjpzd2FwKGFbaV0sIGFbaSsxXSk7CiAgICAgICAgICAgIGZsYWcgPSB0cnVlOwogICAgICAgICB9CiAgICAgIH0KICAgICAgaWYoIWZsYWcpewogICAgICAgICBicmVhazsKICAgICAgfQogICAgICBmbGFnID0gZmFsc2U7CiAgICAgIGVuZC0tOwogICAgICBmb3IoaW50IGkgPSBlbmQgLSAxOyBpID49IHN0YXJ0OyBpLS0pewogICAgICAgICBpZihhW2ldID4gYVtpKzFdKXsKICAgICAgICAgICAgc3RkOjpzd2FwKGFbaV0sIGFbaSsxXSk7CiAgICAgICAgICAgIGZsYWcgPSB0cnVlOwogICAgICAgICB9CiAgICAgIH0KICAgICAgc3RhcnQrKzsKICAgfQp9Cgpkb3VibGUgbWVhc3VyZVRpbWUoc3RkOjp2ZWN0b3I8aW50PiYgYSwgaW50IG4pIHsKICAgIHN0ZWFkeV9jbG9jazo6dGltZV9wb2ludCB0MSA9IHN0ZWFkeV9jbG9jazo6bm93KCk7CiAgICBDb2NrdGFpbFNvcnQoYSwgbik7CiAgICBzdGVhZHlfY2xvY2s6OnRpbWVfcG9pbnQgdDIgPSBzdGVhZHlfY2xvY2s6Om5vdygpOwogICAgZHVyYXRpb248ZG91YmxlPiB0aW1lX3NwYW4gPSBkdXJhdGlvbl9jYXN0PGR1cmF0aW9uPGRvdWJsZT4+KHQyIC0gdDEpOwogICAgZG91YmxlIG1UaW1lID0gdGltZV9zcGFuLmNvdW50KCk7CiAgICBzdGQ6OmNvdXQgPDwgIG1UaW1lIDw8IHN0ZDo6ZW5kbDsKICAgIHJldHVybiBtVGltZTsKfQoKCnZvaWQgRXhwZXJpbWVudChzdGQ6OnZlY3RvcjxpbnQ+ICZhLCBpbnQgbikgewogICAgRmlsbFZlY3RvcihhKTsKICAgIENvY2t0YWlsU29ydChhLCBuKTsKICAgIHN0ZDo6Y291dCA8PCAiXG5cbmEuIFNvcnRlZCBkYXRhOiAiOwogICAgZm9yIChpbnQgaXsgMCB9OyBpIDwgbjsgaSsrKSBzdGQ6OmNvdXQgPDwgYVtpXSA8PCAgJyAnOwoKICAgIGRvdWJsZSogdGltZXMgPSBuZXcgZG91YmxlWzEwMDBdOwogCiAgICBmb3IgKGludCBpPTEwMDsgaSA8IDEwMDA7IGkgKz0gMTAwKSB7CiAgICAgICAgc3RkOjpjb3V0IDw8ICJcblsiIDw8IGkgPDwgIl0iIDw8ICIgIjsKICAgICAgICBmb3IgKGludCBqezF9OyBqIDwgMTA7IGorPTEpIHsKICAgICAgICAgICAgdGltZXNbal0gPSBtZWFzdXJlVGltZShhLCBpKTsKICAgICAgICB9CiAgICB9Cn0KCmludCBtYWluKCkgewogICAgaW50IG57MTAwMH07CiAgICBzdGQ6OnZlY3RvcjxpbnQ+IGEobik7CiAgICBFeHBlcmltZW50KGEsIG4pOwoKICAgIHJldHVybiAwOwp9

Success #stdin #stdout 0.01s 5512KB

stdin

copy

Standard input is empty

stdout

copy


Vector: 55 89 7 9 73 71 8 14 61 25 6 54 67 79 67 64 53 6 57 73 92 65 93 76 34 41 67 47 17 80 66 24 21 25 86 46 96 94 60 57 19 19 64 39 50 83 3 3 41 13 28 85 30 21 61 64 15 81 11 84 61 29 9 83 54 47 29 51 41 42 60 12 13 24 51 63 59 7 66 0 20 95 86 50 68 99 66 35 80 29 20 94 58 81 77 12 28 58 63 21 52 24 33 65 0 85 28 60 44 47 12 64 94 98 66 62 98 32 98 30 13 70 24 71 3 53 83 31 64 99 52 16 75 85 34 27 22 14 39 18 61 52 82 55 2 0 70 0 84 20 83 97 42 7 68 45 13 4 28 77 55 80 45 30 17 79 9 92 94 49 10 7 1 45 63 3 97 85 56 82 5 91 31 47 98 52 92 63 8 20 40 63 52 86 45 21 17 54 65 11 3 28 19 56 25 34 12 22 19 68 56 24 59 88 23 9 92 67 73 0 39 65 63 43 3 8 16 21 14 82 84 18 62 55 26 87 89 38 9 60 6 18 36 17 58 59 79 50 78 4 2 17 69 65 60 25 25 77 46 91 11 82 9 73 38 88 12 79 26 21 92 33 91 28 2 49 88 81 51 18 37 53 36 7 70 96 32 47 25 30 39 36 64 0 61 54 88 73 86 15 47 78 0 38 6 54 40 46 88 43 65 25 97 1 32 19 49 16 67 75 98 6 63 15 58 77 69 47 50 55 14 49 33 66 40 40 20 80 38 8 75 3 34 72 56 18 44 6 87 11 33 37 69 48 52 27 25 22 26 28 29 92 77 15 58 17 7 79 49 45 39 77 49 73 49 5 44 93 63 31 56 96 20 77 97 73 5 22 47 83 2 28 76 80 43 86 49 50 65 51 96 5 28 97 30 29 54 26 75 18 9 83 66 30 61 15 3 18 38 2 1 40 30 29 72 74 16 74 24 33 77 72 90 5 69 73 86 24 99 13 94 9 97 12 39 58 28 94 76 18 96 29 58 26 11 83 0 79 57 77 12 34 49 55 91 19 28 29 95 79 43 89 88 40 53 79 50 81 73 26 99 69 7 10 96 18 93 48 49 2 25 62 88 27 69 31 46 97 60 93 76 3 34 17 43 87 96 93 69 70 71 20 39 31 30 87 1 75 88 51 29 13 65 69 40 34 0 38 83 61 31 11 16 17 28 12 5 77 57 26 47 81 46 38 12 29 78 65 56 66 16 38 31 33 7 72 67 8 62 2 21 46 14 89 63 94 1 20 71 11 46 70 92 45 9 56 26 39 21 82 5 38 20 36 23 28 60 91 88 75 45 61 21 59 2 36 6 56 57 77 67 3 0 59 0 9 67 26 0 88 61 5 78 81 93 2 61 54 45 1 29 90 14 2 2 17 38 8 73 95 37 40 51 37 51 51 98 18 30 98 58 91 55 37 24 49 39 38 55 84 91 36 26 6 38 28 75 28 36 48 76 74 40 27 63 43 30 62 13 12 60 71 55 16 8 80 17 99 18 72 35 61 8 62 67 98 90 42 78 79 42 54 5 82 33 68 25 64 82 38 28 95 62 84 63 22 64 80 22 34 52 57 95 12 71 15 62 14 57 40 93 0 95 50 34 28 70 12 44 53 2 73 48 64 9 11 87 73 43 61 59 47 70 6 59 42 21 73 8 31 13 1 83 60 3 17 41 73 81 85 78 84 10 26 0 19 89 39 44 84 0 55 31 71 62 42 65 35 15 73 66 81 26 49 41 29 19 34 54 0 72 33 36 34 11 37 54 53 28 50 37 29 58 69 52 20 11 17 55 79 42 74 60 68 75 53 49 94 40 3 47 12 88 83 46 0 72 52 5 1 55 42 82 13 63 34 85 27 3 92 6 45 66 18 13 42 23 14 88 63 17 35 75 58 71 22 58 43 26 63 96 81 57 78 94 21 64 79 0 67 72 6 64 90 24 29 84 99 43 73 63 13 8 38 71 79 12 81 75 91 96 23 72 53 54 19 26 18 50 26 38 74 84 2 17 60 32 1 60 27 74 23 40 35 13 11 14 26 92 41 69 88 65 41 94 19 12 72 89 15 99 79 41 35 82 58 96 66 60 56 93 34 79 86 69 44 49 36 70 94 29 39 34 46 33 28 65 97 53 7 12 4 86 54 39 20 64 35 86 24 43 32 11 74 70 32 19 19 68 89 13 50 81 48 96 66 28 14 15 81 21 80 85 59 34 77 80 50 12 18 

a. Sorted data: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 16 16 16 16 16 16 16 17 17 17 17 17 17 17 17 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 19 20 20 20 20 20 20 20 20 20 20 20 21 21 21 21 21 21 21 21 21 21 21 21 22 22 22 22 22 22 22 23 23 23 23 23 24 24 24 24 24 24 24 24 24 24 25 25 25 25 25 25 25 25 25 25 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 27 27 27 27 27 27 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 30 30 30 30 30 30 30 30 30 30 31 31 31 31 31 31 31 31 31 32 32 32 32 32 32 33 33 33 33 33 33 33 33 33 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 35 35 35 35 35 35 35 36 36 36 36 36 36 36 36 36 37 37 37 37 37 37 37 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 39 39 39 39 39 39 39 39 39 39 39 39 40 40 40 40 40 40 40 40 40 40 40 40 41 41 41 41 41 41 41 41 42 42 42 42 42 42 42 42 42 43 43 43 43 43 43 43 43 43 43 44 44 44 44 44 44 45 45 45 45 45 45 45 45 45 46 46 46 46 46 46 46 46 46 47 47 47 47 47 47 47 47 47 47 47 48 48 48 48 48 49 49 49 49 49 49 49 49 49 49 49 49 49 49 50 50 50 50 50 50 50 50 50 50 50 51 51 51 51 51 51 51 51 52 52 52 52 52 52 52 52 52 53 53 53 53 53 53 53 53 53 54 54 54 54 54 54 54 54 54 54 54 54 55 55 55 55 55 55 55 55 55 55 55 55 56 56 56 56 56 56 56 56 56 57 57 57 57 57 57 57 57 58 58 58 58 58 58 58 58 58 58 58 58 59 59 59 59 59 59 59 59 60 60 60 60 60 60 60 60 60 60 60 60 60 61 61 61 61 61 61 61 61 61 61 61 61 62 62 62 62 62 62 62 62 62 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 64 64 64 64 64 64 64 64 64 64 64 64 65 65 65 65 65 65 65 65 65 65 65 65 66 66 66 66 66 66 66 66 66 66 66 67 67 67 67 67 67 67 67 67 67 68 68 68 68 68 68 69 69 69 69 69 69 69 69 69 69 69 70 70 70 70 70 70 70 70 70 71 71 71 71 71 71 71 71 71 72 72 72 72 72 72 72 72 72 72 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 74 74 74 74 74 74 74 75 75 75 75 75 75 75 75 75 75 76 76 76 76 76 77 77 77 77 77 77 77 77 77 77 77 77 78 78 78 78 78 78 78 79 79 79 79 79 79 79 79 79 79 79 79 79 79 80 80 80 80 80 80 80 80 80 81 81 81 81 81 81 81 81 81 81 81 81 82 82 82 82 82 82 82 82 82 83 83 83 83 83 83 83 83 83 83 84 84 84 84 84 84 84 84 84 85 85 85 85 85 85 85 86 86 86 86 86 86 86 86 86 87 87 87 87 87 88 88 88 88 88 88 88 88 88 88 88 88 88 89 89 89 89 89 89 89 90 90 90 90 91 91 91 91 91 91 91 91 92 92 92 92 92 92 92 92 92 93 93 93 93 93 93 93 93 94 94 94 94 94 94 94 94 94 94 94 95 95 95 95 95 95 96 96 96 96 96 96 96 96 96 96 96 97 97 97 97 97 97 97 97 98 98 98 98 98 98 98 98 99 99 99 99 99 99 99 
[100] 2.66e-07
1.84e-07
1.51e-07
1.44e-07
1.51e-07
1.57e-07
1.49e-07
1.52e-07
1.45e-07

[200] 2.65e-07
2.58e-07
2.54e-07
2.54e-07
2.52e-07
2.55e-07
2.51e-07
2.56e-07
2.51e-07

[300] 3.62e-07
3.51e-07
3.57e-07
3.54e-07
3.48e-07
3.47e-07
6.204e-06
3.47e-07
3.52e-07

[400] 4.52e-07
4.55e-07
4.55e-07
4.53e-07
4.54e-07
4.55e-07
4.55e-07
4.55e-07
4.56e-07

[500] 5.57e-07
5.58e-07
5.54e-07
5.57e-07
5.56e-07
5.55e-07
5.55e-07
5.54e-07
5.52e-07

[600] 6.55e-07
6.54e-07
6.48e-07
6.49e-07
6.49e-07
6.51e-07
6.53e-07
6.47e-07
6.5e-07

[700] 7.49e-07
7.55e-07
7.5e-07
7.47e-07
7.51e-07
7.47e-07
7.44e-07
7.44e-07
7.46e-07

[800] 8.53e-07
8.53e-07
8.47e-07
8.5e-07
8.5e-07
8.5e-07
8.47e-07
8.47e-07
8.5e-07

[900] 9.49e-07
9.5e-07
9.44e-07
9.44e-07
9.44e-07
9.46e-07
9.47e-07
9.48e-07
9.44e-07

https://ideone.com/GgHXvZ

language:

C++ (gcc 8.3)

created:

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!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language