Compare sorting algorithms' performance: Difference between revisions

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

=={{header|Haskell}}==

import Data.List

where

step x = (x * a + c) `mod` m

As a result of testing we get the list of tuples: length of a list and time in microseconds:

Different sorting methods:

qsort :: Ord a => Sorter a

qsort [] = []

-- Insertion sort

isort :: Ord a => Sorter a

Finally, charting routines and the task implementation:

barChart :: Char -> [(Int, Time)] -> [String]

barChart ch lst = bar . scale <$> lst

run rand

where

<pre>λ> main

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

=={{header|JavaScript}}==

function swap(a, i, j){

var t = a[i]

console.log(sOut)

{{out}}

<pre>

=={{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"])

println("Average sort times for 40000 randomized:")

println("\tinsertion sort:\t$iavg\n\tmerge sort:\t$mavg\n\tquick sort\t$qavg")

<pre>Average sort times for 40000 ones:

insertion sort: 0.00036058316000000005

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

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

ListLogLogPlot[Transpose@times[[All,1]],PlotLegends->{"Bubble","Shell"},PlotLabel->"Ones"]

ListLogLogPlot[Transpose@times[[All,2]],PlotLegends->{"Bubble","Shell"},PlotLabel->"Ascending integers"]

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

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

stdout.write &"{time:8d} "

echo ""

{{out}}

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

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

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

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.*/

if i==2 then i= 1

else i= i * 5 % 11

{{out|output|text=&nbsp; when using the default inputs:}}

=={{header|Ruby}}==

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

ary = dup

puts

end

Array#sort is a built-in method.

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

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

}

System.print("\n")

{{out}}