What Speed is our Selection-Sort Program?
This is the latest version of the program, showing only main and
the sort function
void sort(string * A, int N)
{ while (N > 1)
{ int pos = 0;
for (int i = 1; i < N; i += 1)
{ if (A[i] > A[pos])
pos = i; }
swap(A[pos], A[N-1]);
N -= 1; } }
int main(int argc, char * argv[])
{ int size = atol(argv[1]);
string * data = new string[size];
srandomdev();
for (int i = 0; i < size; i += 1)
data[i] = random_string(12);
double t1 = getcputime();
sort(data, size);
double t2 = getcputime();
cout << "it took " << t2-t1 << " seconds to sort " << size << " things\n"; }
And this is the "doit" file that automates the testing
a.out 100
a.out 200
a.out 300
a.out 400
a.out 500
a.out 600
a.out 700
a.out 800
a.out 900
a.out 1000
a.out 1200
a.out 1400
a.out 1600
a.out 1800
a.out 2000
a.out 3000
a.out 4000
a.out 5000
a.out 6000
a.out 7000
a.out 8000
a.out 9000
These are the results
it took 0.000274 seconds to sort 100 things
it took 0.001037 seconds to sort 200 things
it took 0.002304 seconds to sort 300 things
it took 0.004077 seconds to sort 400 things
it took 0.006418 seconds to sort 500 things
it took 0.009324 seconds to sort 600 things
it took 0.012725 seconds to sort 700 things
it took 0.016685 seconds to sort 800 things
it took 0.021185 seconds to sort 900 things
it took 0.026147 seconds to sort 1000 things
it took 0.037734 seconds to sort 1200 things
it took 0.051452 seconds to sort 1400 things
it took 0.067312 seconds to sort 1600 things
it took 0.085098 seconds to sort 1800 things
it took 0.10514 seconds to sort 2000 things
it took 0.236719 seconds to sort 3000 things
it took 0.421157 seconds to sort 4000 things
it took 0.658994 seconds to sort 5000 things
it took 0.947822 seconds to sort 6000 things
it took 1.29173 seconds to sort 7000 things
it took 1.68926 seconds to sort 8000 things
it took 2.14017 seconds to sort 9000 things
And this is those results plotted on log-log graph paper.
To fit on the paper's three vertical decades, the measurements
for 100, 7000, 8000, and 9000 have to be left out.
The points make a perfect straight line, exactly parallel to
the "2" diagonal, so it is definitely a quadratic. The time taken
to sort depends on the square of the number of things being sorted.