Compare sorting algorithms' performance: Difference between revisions
Compare sorting algorithms' performance (view source)
Revision as of 20:26, 26 August 2022
, 1 year agosyntax highlighting fixup automation
No edit summary |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 34:
=={{header|AutoHotkey}}==
{{in progress|lang=AutoHotkey|day=16|month=1|year=2010}}
<
#Persistent
Line 337:
Sort, var, N D`,
Return var
}</
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
INSTALL @lib$+"SORTLIB"
INSTALL @lib$+"TIMERLIB"
Line 503:
ENDWHILE
a%() += l%
ENDPROC</
'''Output:'''
<pre>
Line 547:
===Sequence generators===
<tt>csequence.h</tt>
<
#define _CSEQUENCE_H
#include <stdlib.h>
Line 555:
void fillwithrrange(double *v, int n);
void shuffledrange(double *v, int n);
#endif</
<tt>csequence.c</tt>
<
static double fill_constant;
Line 587:
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"
Line 630:
};
typedef struct seqdef seqdef_t;
#endif</
<tt>writetimings.c</tt>
<
#include <stdlib.h>
Line 735:
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>
Line 768:
return 0;
}</
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>
Line 794:
=={{header|D}}==
<
std.random, std.typetuple;
Line 941:
nRuns.benchmark!(randomBubble, randomInsertion,
randomHeap, randomBuiltIn).show;
}</
{{out}}
<pre>Timings in microseconds:
Line 966:
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.
<syntaxhighlight lang="erlang">
-module( compare_sorting_algorithms ).
Line 994:
{Time, _Result} = timer:tc( fun() -> Fun( List_fun(N) ) end ),
{math:log10(N), math:log10(Time)}.
</syntaxhighlight>
=={{header|Go}}==
{{libheader|gonum/plot}}
<
import (
Line 1,219:
ps.Shape = plotutil.DefaultGlyphShapes[dx]
p.Add(pl, ps)
}</
{{out}}
[[file:GoComp.png|right|Comparison]]
Line 1,230:
=={{header|Haskell}}==
<
import Data.List
Line 1,259:
where
step x = (x * a + c) `mod` m
(a, c, m) = (1103515245, 12345, 2^31-1)</
As a result of testing we get the list of tuples: length of a list and time in microseconds:
Line 1,269:
Different sorting methods:
<
qsort :: Ord a => Sorter a
qsort [] = []
Line 1,285:
-- Insertion sort
isort :: Ord a => Sorter a
isort = foldr insert []</
Finally, charting routines and the task implementation:
<
barChart :: Char -> [(Int, Time)] -> [String]
barChart ch lst = bar . scale <$> lst
Line 1,326:
run rand
where
run = comparison [sort, isort, qsort, bsort] "siqb"</
<pre>λ> main
Line 1,482:
=={{header|J}}==
<syntaxhighlight lang="j">
NB. extracts from other rosetta code projects
ts=: 6!:2, 7!:2@]
Line 1,565:
(_*pts) + n +./ .*1 0 2|:coef&(p."1) plot x
)
</syntaxhighlight>
<pre>
Line 1,718:
=={{header|JavaScript}}==
<
function swap(a, i, j){
var t = a[i]
Line 1,904:
console.log(sOut)
</syntaxhighlight>
{{out}}
<pre>
Line 1,935:
=={{header|Julia}}==
Julia comes with the InsertionSort, MergeSort, and QuickSort routines built into the Base.Sort module. Here is a comparison using those system algorithms and with integers.
<
function comparesorts(tosort)
a = shuffle(["i", "m", "q"])
Line 1,972:
println("Average sort times for 40000 randomized:")
println("\tinsertion sort:\t$iavg\n\tmerge sort:\t$mavg\n\tquick sort\t$qavg")
</syntaxhighlight>
<pre>Average sort times for 40000 ones:
insertion sort: 0.00036058316000000005
Line 1,997:
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
Line 2,138:
println("\n")
}
}</
{{out}}
Line 2,177:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Comparing bubble and shell sort:
<
BubbleSort[in_List]:=Module[{x=in,l=Length[in],swapped},swapped=True;
While[swapped,swapped=False;
Line 2,204:
ListLogLogPlot[Transpose@times[[All,1]],PlotLegends->{"Bubble","Shell"},PlotLabel->"Ones"]
ListLogLogPlot[Transpose@times[[All,2]],PlotLegends->{"Bubble","Shell"},PlotLabel->"Ascending integers"]
ListLogLogPlot[Transpose@times[[All,3]],PlotLegends->{"Bubble","Shell"},PlotLabel->"Shuffled"]</
{{out}}
Outputs three graphs on a log-log scales showing the size of the array and the time taken, for each of the three different arrays.
Line 2,215:
We have also added the array as first parameter of the internal function “sorter” as Nim compiler doesn’t allow direct access to this mutable array in function “quicksort” (memory safety violation).
<
import random
import sequtils
Line 2,367:
stdout.write &"{time:8d} "
echo ""
echo '\n'</
{{out}}
Line 2,408:
=={{header|Phix}}==
{{libheader|Phix/pGUI}}
<!--<
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Compare_sorting_algorithms.exw</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">XQS</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">01</span> <span style="color: #000080;font-style:italic;">-- (set to 1 to exclude quick_sort and shell_sort from ones)</span>
Line 2,765:
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</
===Conclusions===
I knew bubblesort and insertion sort would be bad, but not so bad that you cannot meaningfully plot them against better sorts.
Line 2,782:
{{works with|Python|2.5}}
===Examples of sorting routines===
<
x.sort()
Line 2,800:
if size < 2: return seq
low, middle, up = partition(seq, random.choice(seq))
return qsortranpart(low) + middle + qsortranpart(up)</
===Sequence generators===
<
return [1]*n
Line 2,813:
x = range(n)
random.shuffle(x)
return x</
===Write timings===
<
sequence_creators = (ones, range, shuffledrange)):
Ns = range(2, maxN, maxN//npoints)
Line 2,821:
for make_seq in sequence_creators:
Ts = [usec(sort, (make_seq(n),)) for n in Ns]
writedat('%s-%s-%d-%d.xy' % (sort.__name__, make_seq.__name__, len(Ns), max(Ns)), Ns, Ts)</
Where ''writedat()'' is defined in the [[Write float arrays to a text file]], ''usec()'' - [[Query Performance]], ''insertion_sort()'' - [[Insertion sort]], ''qsort'' - [[Quicksort]] subtasks, correspondingly.
Line 2,827:
{{libheader|matplotlib}}
{{libheader|NumPy}}
<
import numpy, pylab
def plotdd(dictplotdict):
Line 2,849:
pylab.savefig(figname+'.png')
pylab.savefig(figname+'.pdf')
print figname</
See [[Plot x, y arrays]] and [[Polynomial Fitting]] subtasks for a basic usage of ''pylab.plot()'' and ''numpy.polyfit()''.
<
import numpy
def plot_timings():
Line 2,881:
# actual plotting
plotdd(df)
plotdd(ds) # see ``plotdd()`` above</
===Figures: log2( time in microseconds ) vs. log2( sequence length )===
Line 2,887:
[[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]]
Line 2,904:
sort_functions=sort_functions,
sequence_creators = (ones, range, shuffledrange))
plot_timings()</
Executing above script we get belowed figures.
====ones====
Line 2,935:
The number of ranges can be increased at the expense of a wider display of output.
<
parse arg ranges start# seed . /*obtain optional arguments from the CL*/
if ranges=='' | ranges=="," then ranges= 5 /*Not Specified? Then use the default.*/
Line 3,206:
if i==2 then i= 1
else i= i * 5 % 11
end /*while i¬==0*/; return</
{{out|output|text= when using the default inputs:}}
Line 3,232:
=={{header|Ruby}}==
<
def radix_sort(base=10) # negative value is inapplicable.
ary = dup
Line 3,324:
puts
end
end</
Array#sort is a built-in method.
Line 3,376:
{{libheader|Tk}}
{{tcllib|struct::list}}
<
# measure and plot times
package require Tk
Line 3,597:
create_log10_plot "Sorting a '$type' list" size time $sizes $times $algorithms $shapes $colours
}
puts "\ntimes in microseconds, average of $runs runs"</
{{omit from|GUISS}}
Line 3,646:
Results presented in tabular form as Wren doesn't have a plotting library available at the present time.
<
import "/sort" for Sort
import "/fmt" for Fmt
Line 3,768:
}
System.print("\n")
}</
{{out}}
|