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|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

INSTALL @lib$+"SORTLIB"

INSTALL @lib$+"TIMERLIB"

ENDWHILE

a%() += l%

'''Output:'''

<pre>

===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>

 

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>

 

=={{header|D}}==

std.random, std.typetuple;

 

nRuns.benchmark!(randomBubble, randomInsertion,

randomHeap, randomBuiltIn).show;

{{out}}

<pre>Timings in microseconds:

The sort routines are borrowed from [http://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort bubble sort], [http://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort insertion sort] and [http://rosettacode.org/wiki/Sorting_algorithms/Quicksort quick sort]. Plots by [https://github.com/psyeugenic/eplot eplot].

Bubble sort does [http://github.com/ebengt/rosettacode/tree/master/graphs/ones.png ones] and [http://github.com/ebengt/rosettacode/tree/master/graphs/ranges.png ranges] best. Insertion sort does [http://github.com/ebengt/rosettacode/tree/master/graphs/reversed_ranges.png reversed ranges] best. Quick sort handles [http://github.com/ebengt/rosettacode/tree/master/graphs/shuffleds.png shuffled numbers] best.

-module( compare_sorting_algorithms ).

 

{Time, _Result} = timer:tc( fun() -> Fun( List_fun(N) ) end ),

{math:log10(N), math:log10(Time)}.

 

=={{header|Go}}==

{{libheader|gonum/plot}}

 

import (

ps.Shape = plotutil.DefaultGlyphShapes[dx]

p.Add(pl, ps)

{{out}}

[[file:GoComp.png|right|Comparison]]

On random data (triangles) insertion and bubble sort show worse performance than quicksort.

<br clear=all>

 

=={{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|Kotlin}}==

 

Although it would be easy enough to plot the results graphically using an external library such as JFreePlot, there doesn't seem much point when we can no longer upload images to RC. I've therefore presented the results in tabular form on the terminal which is good enough to detect significant trends.

 

import java.util.Random

println("\n")

}

 

{{out}}

On the other hand, bubble and insertion sorts are much quicker than the other methods for constant data and for data which is already sorted in an ascending direction, bubble sort being the faster of the two.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

===Conclusions===

(logarithmic scale helps, but is still not enough)

I had no idea that (these particular implementations of) quicksort and shellsort would be so bad on a sequence of all 1s.

{{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.

 

{{libheader|matplotlib}}

{{libheader|NumPy}}

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|Ruby}}==

def radix_sort(base=10) # negative value is inapplicable.

ary = dup

puts

end

Array#sort is a built-in method.

 

insertion_sort 0.053 5.298 --.--- --.---

bubble_sort 0.206 17.232 --.--- --.---

</pre>

 

{{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

}

 

{{omit from|GUISS}}

[[Image:Tcl_sort_reversed.png]]

[[Image:Tcl_sort_random.png]]