Compare sorting algorithms' performance: Difference between revisions
Content added Content deleted
m (→Plot timings and Figures: gnuplot nothing to do with GNU (!!)) |
m (→Write timings: GNU 2 Gnu) |
||
| Line 222: | Line 222: | ||
This code produce several files with the following naming convention: |
This code produce several files with the following naming convention: |
||
* data_''algorithm''_''sequence''.dat |
* data_''algorithm''_''sequence''.dat |
||
Where ''algorithm'' is one of the following: insertion, merge, shell, quick, qsort (the quicksort in the libc library) (bubble sort became too slow for longest sequences). ''Sequence'' is ''c1'' (constant value 1), ''rr'' (reverse range), ''sr'' (shufled range). These data can be easily plotted by |
Where ''algorithm'' is one of the following: insertion, merge, shell, quick, qsort (the quicksort in the libc library) (bubble sort became too slow for longest sequences). ''Sequence'' is ''c1'' (constant value 1), ''rr'' (reverse range), ''sr'' (shufled range). These data can be easily plotted by Gnuplot, which can also do fitting. Instead we do our fitting using [[Polynomial Fitting]]. |
||
<lang c>#include <stdio.h> |
<lang c>#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
| Line 255: | Line 255: | ||
Here we search for a fit with C<sub>0</sub>+C<sub>1</sub>x "in the log scale", since we supposed the data, once plotted on a logscale graph, can be fitted by a line. We can use e.g. a shell one-liner to produce the parameters for the line for each data file previously output. In particular I've used the following |
Here we search for a fit with C<sub>0</sub>+C<sub>1</sub>x "in the log scale", since we supposed the data, once plotted on a logscale graph, can be fitted by a line. We can use e.g. a shell one-liner to produce the parameters for the line for each data file previously output. In particular I've used the following |
||
<pre>for el in *.dat ; do fitdata <$el >${el%.dat}.fd ; done</pre> |
<pre>for el in *.dat ; do fitdata <$el >${el%.dat}.fd ; done</pre> |
||
===Plot timings and Figures=== |
===Plot timings and Figures=== |
||
Once we have all the ".dat" files and associated ".fd", we can use Gnuplot to draw our '''data''' and think about conclusions (we could also use the idea in [[Plot x, y arrays]], but it needs too much enhancements to be usable for this analysis). Here an example of such a draw for a single file (using Gnuplot) |
Once we have all the ".dat" files and associated ".fd", we can use Gnuplot to draw our '''data''' and think about conclusions (we could also use the idea in [[Plot x, y arrays]], but it needs too much enhancements to be usable for this analysis). Here an example of such a draw for a single file (using Gnuplot) |
||