Compare sorting algorithms' performance: Difference between revisions

Measure a relative performance of sorting algorithms implementations.

 

 

Consider three type of input sequences:

 

Consider at least two different sorting functions (different algorithms or/and different implementation of the same algorithm).

 

Preliminary subtask:

 

General steps:

 

=={{header|AutoHotkey}}==

{{in progress|lang=AutoHotkey|day=16|month=1|year=2010}}

 

#Persistent

Sort, var, N D`,

Return var

 

=={{header|C}}==

===Sequence generators===

<tt>csequence.h</tt>

#define _CSEQUENCE_H

#include <stdlib.h>

void fillwithrrange(double *v, int n);

void shuffledrange(double *v, int n);

<tt>csequence.c</tt>

 

static double fill_constant;

v[r] = t;

}

===Write timings===

We shall use the code from [[Query Performance]]. Since the ''action'' is a generic function with a single argument, we need ''wrappers'' which encapsule each sorting algorithms we want to test.

 

<tt>writetimings.h</tt>

#define _WRITETIMINGS_H

#include "sorts.h"

};

typedef struct seqdef seqdef_t;

<tt>writetimings.c</tt>

#include <stdlib.h>

 

int doublecompare( const void *a, const void *b )

{

}

int action_qsort(int size)

free(tobesorted);

return 0;

This code produce several files with the following naming convention:

* 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 Gnuplot, which can also do fitting. Instead we do our fitting using [[Polynomial Fitting]].

#include <stdlib.h>

#include <math.h>

 

return 0;

Here we search for a fit with C₀+C₁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>

* [http://i43.tinypic.com/2nqrzfs.png reversed range]

* [http://i41.tinypic.com/24q8hmg.png shuffled range]

 

=={{header|J}}==

NB. extracts from other rosetta code projects

ts=: 6!:2, 7!:2@]

(_*pts) + n +./ .*1 0 2|:coef&(p."1) plot x

)

 

<pre>

 

The data fit curves of the character cell graph were combined with GCD +. function. This explains "1"s or other strange values where these curves intersect. Finally the scatter plots were multiplied by infinity and added to the best fit curves. The points didn't show up well using the same values as the curves.

 

=={{header|Python}}==

{{works with|Python|2.5}}

===Examples of sorting routines===

x.sort()

 

if size < 2: return seq

low, middle, up = partition(seq, random.choice(seq))

 

===Sequence generators===

 

return [1]*n

 

x = range(n)

random.shuffle(x)

===Write timings===

sequence_creators = (ones, range, shuffledrange)):

Ns = range(2, maxN, maxN//npoints)

for make_seq in sequence_creators:

Ts = [usec(sort, (make_seq(n),)) for n in Ns]

Where ''writedat()'' is defined in the [[Write float arrays to a text file]], ''usec()'' - [[Query Performance]], ''insertion_sort()'' - [[Insertion sort]], ''qsort'' - [[Quicksort]] subtasks, correspondingly.

 

===Plot timings===

{{libheader|matplotlib}}

import numpy, pylab

def plotdd(dictplotdict):

pylab.savefig(figname+'.png')

pylab.savefig(figname+'.pdf')

See [[Plot x, y arrays]] and [[Polynomial Fitting]] subtasks for a basic usage of ''pylab.plot()'' and ''numpy.polyfit()''.

 

import numpy

def plot_timings():

# actual plotting

plotdd(df)

 

===Figures: log2( time in microseconds ) vs. log2( sequence length )===

[[File:Range.png|300px|thumb|right|log(Time) vs. log(N): Relative performance on range(N) as an input]]

[[File:Shuffledrange.png|300px|thumb|right|log(Time) vs. log(N): Relative performance on random permutation of range(N) as an input]]

builtinsort, # see implementation above

insertion_sort, # see [[Insertion sort]]

sort_functions=sort_functions,

sequence_creators = (ones, range, shuffledrange))

Executing above script we get belowed figures.

====ones====

qsort - O(N*log(N))

qsortranpart - O(N) ???

 

=={{header|Tcl}}==

{{libheader|Tk}}

{{tcllib|struct::list}}

# measure and plot times

package require Tk

create_log10_plot "Sorting a '$type' list" size time $sizes $times $algorithms $shapes $colours

}

 

===Output===

[[Image:Tcl_sort_reversed.png]]

[[Image:Tcl_sort_random.png]]