C++

Forum

 
Time duration of a bubble sort process

mpg (87)
Hello I am new to c++ . I am studing c++ from few months and I need at school to calculate the time duration of the only bubble sort process

THe bubble sort code must be absolutely this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <chrono>


using namespace std;

int main()
{


const int n = 5;
int vet[n];
int tmp;
srand(time(NULL));
for(int i=0;i<n;i++)
    vet[i] = rand() % 100;

cout<<endl;
bool flag = true;
int stop = n - 1;

while (flag)
{
    flag = false;
    for (int i = 0; i <= stop; i++)
        if (vet[i] > vet[i + 1])
        {
            tmp=vet[i];
            vet[i]=vet[i+1];
            vet[i+1]=tmp;
            flag = true;
        }

    stop = stop - 1;
}
for(int i=0;i<n; i++)
{
    cout<<vet[i]<<endl;
}
}


If I use
auto inizio = high_resolution_clock::now();
code....
auto fine = high_resolution_clock::now();
cout << duration_cast<duration<double>>(fine - inizio).count() << endl;

the time of sort is always 0 or like 0-20004555 not for example 0.0856 sec.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
#include <iostream>
#include <ctime>
#include<cstdlib>
#include <chrono>
using namespace std;
using namespace chrono;

int main()


{
    srand(time(NULL));



const int n = 10;
int vet[n];
int tmp;
for(int i=0;i<n;i++)
{
    vet[i]=rand()%9;
}

cout<<endl;
bool flag =  true;
int stop = n - 1;

auto puntoA = high_resolution_clock::now();
while (flag)
{
    flag = false;
    for (int i = 0; i <= stop; i++)
        if (vet[i] > vet[i + 1])
        {

            tmp=vet[i];
            vet[i]=vet[i+1];
            vet[i+1]=tmp;
            flag = true;
        }

    stop = stop - 1;
}


{
      auto puntoB = high_resolution_clock::now();

cout << "tempo del sort :   "<<duration_cast<duration<double>>(puntoB - puntoA).count();

}
for (int i = 0; i < n; i++)
cout<<vet[i]<<endl;

}


Help me!!!!
Last edited on
keskiverto (10363)
Your n=10. The amount of instructions to sort 10 values is minuscule even in the worst case. I bet your CPU can do much more instructions within one (high resolution) timestep.
doug4 (1534)
I need at school to calculate the time duration of the only bubble sort process


Are you supposed to calculate the time duration or the time complexity? Actual duration of a single function call is rarely of interest. It's the complexity--the rate at which the duration increases as the data set increases--that's more interesting to computer scientists.

Try running the program with n = 1 million, 2 million, 5 million, 10 million, 100 million, 1 billion. Then plot the data size vs. run time to see how the duration behaves.

By the way, when working with the huge data sets, you probably don't want to use the % operator in line 21--just use the full int.
jonnin (11331)
the only way to measure such tiny run times is to get the cpu clock cycles, as far as I know, which may be a bit of trouble depending on your platform.

Its easier to just do what doug4 said and plot a small curve.

when I studied bubble sort, 1000 items took a couple of hours, lol.

ne555 (10692)
1
2
3
 
    int stop = n - 1;
    for (int i = 0; i <= stop; i++)
        if (vet[i] > vet[i + 1])
out of bounds access.
poteto (525)
Using a primitive as duration type, will give you weird results. If you want to avoid results like 4.98e-07 use std::duration<float, std::chrono::milliseconds::period>.
Topic archived. No new replies allowed.