Programming and Graphics

5.3 Sorting with the STL 139

Order of an algorithm

We can assess the performance of thesortfunction by studying the
relation between the elapsed CPU time and the list size,N. The following code
contained in fileransort.ccgenerates and sorts a random list of integers:

#include <algorithm>

using namespace std;

int main()

{

const int N=1048*1048*2;

int randominteger[N];

for(int i=1;i<=N;i++)

{

randominteger[i] = rand();

}

sort(randominteger, randominteger+N+1);

return 0;

}

Now we compile the code into the executableransort, and issue the Unix com-
mand:

time ransort

On execution, we see on the screen:

0.664u 0.020s 0:00.70 97.1% 0+0k 0+0io 0pf+0w

The first field is the CPU time used by the program (user), the second field is
the CPU time used by the operating system in support of the program (system),
and the third field is total CPU time (user and system). The significance of
the rest of the fields is explained in thetimemanual invoked by issuing the
command:man time.

Running the program with list sizeN=2^19 , 220 , and 2^21 , requires, res-
pectively, 0.180u, 0.312u, and 0.652u of CPU time. We observe that, asNis
doubled, the CPU time also nearly doubles, which means that the algorithm
implemented insortis almost linear. In fact, analysis shows that the CPU
time scales withNlogN. By contrast, if we had used the bubble-sort algo-
rithm discussed in Chapter 3, we would have found that the CPU scales with
N^2 , which is much inferior.