Rosetta Code

Compare sorting algorithms' performance: Difference between revisions

Page Discussion

Compare sorting algorithms' performance (view source)

Revision as of 16:00, 15 December 2023

14,794 bytes added ,  5 months ago
Added Sidef
No edit summary
(Added Sidef)
 
(4 intermediate revisions by 4 users not shown)
Line 34:
=={{header|AutoHotkey}}==
{{in progress|lang=AutoHotkey|day=16|month=1|year=2010}}
<langsyntaxhighlight lang="ahk">; BUGGY - FIX
 
#Persistent
Line 337:
Sort, var, N D`,
Return var
}</langsyntaxhighlight>
 
 
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">#Macro sort_1(sortname)
Rset buffer, #sortname
Print buffer;
copy_array(rev(), sort())
t1 = Timer
sortname(sort())
t2 = Timer - t1
Print Using " ###.###&"; t2; " sec";
copy_array(ran(), sort())
t1 = Timer
sortname(sort())
t2 = Timer - t1
Print Using " ###.###&"; t2; " sec";
t1 = Timer
sortname(sort())
t2 = Timer - t1
Print Using " ###.###&"; t2; " sec";
copy_array(eq(), sort())
t1 = Timer
sortname(sort())
t2 = Timer - t1
Print Using " ###.###&"; t2; " sec"
#EndMacro
 
#Macro sort_2(sortname)
Rset buffer, #sortname
Print buffer;
copy_array(rev(), sort())
t1 = Timer
sortname(sort(), Lbound(sort), Ubound(sort))
t2 = Timer - t1
Print Using " ###.###&"; t2; " sec";
copy_array(ran(), sort())
t1 = Timer
sortname(sort(), Lbound(sort), Ubound(sort))
t2 = Timer - t1
Print Using " ###.###&"; t2; " sec";
t1 = Timer
sortname(sort(), Lbound(sort), Ubound(sort))
t2 = Timer - t1
Print Using " ###.###&"; t2; " sec";
copy_array(eq(),sort())
t1 = Timer
sortname(sort(), Lbound(sort), Ubound(sort))
t2 = Timer - t1
Print Using " ###.###&"; t2; " sec"
#EndMacro
 
 
Sub bubbleSort(array() As Double)
Dim As Integer i, lb = Lbound(array), ub = Ubound(array)
For p1 As Uinteger = 0 To ub - 1
For p2 As Uinteger = p1 + 1 To ub
'change >= to > , don't swap if they are equal
If (array(p1)) > (array(p2)) Then Swap array(p1), array(p2)
Next p2
Next p1
For i = lb To ub - 1
If array(i) > array(i + 1) Then Beep
Next
End Sub
 
Sub exchangeSort(array() As Double)
Dim As Uinteger i, j, min, ub = Ubound(array)
For i = 0 To ub
min = i
For j = i+1 To ub
If (array(j) < array(min)) Then min = j
Next j
If min > i Then Swap array(i), array(min)
Next i
End Sub
 
Sub insertionSort(array() As Double)
Dim As Uinteger ub = Ubound(array)
Dim As Uinteger i, j, temp, temp2
For i = 1 To ub
temp = array(i)
temp2 = temp
j = i
While j >= 1 Andalso array(j-1) > temp2
array(j) = array(j - 1)
j -= 1
Wend
array(j) = temp
Next i
End Sub
 
Sub siftdown(hs() As Double, inicio As Ulong, final As Ulong)
Dim As Ulong root = inicio
Dim As Long lb = Lbound(hs)
While root * 2 + 1 <= final
Dim As Ulong child = root * 2 + 1
If (child + 1 <= final) Andalso (hs(lb + child) < hs(lb + child + 1)) Then child += 1
If hs(lb + root) < hs(lb + child) Then
Swap hs(lb + root), hs(lb + child)
root = child
Else
Return
End If
Wend
End Sub
Sub heapSort(array() As Double)
Dim As Long lb = Lbound(array)
Dim As Ulong count = Ubound(array) - lb + 1
Dim As Long inicio = (count - 2) \ 2
Dim As Ulong final = count - 1
While inicio >= 0
siftdown(array(), inicio, final)
inicio -= 1
Wend
While final > 0
Swap array(lb + final), array(lb)
final -= 1
siftdown(array(), 0, final)
Wend
End Sub
 
Sub shellSort(array() As Double)
Dim As Uinteger lb = Lbound(array), ub = Ubound(array)
Dim As Uinteger i, inc = ub - lb
Dim As Boolean done
Do
inc = Int(inc / 2.2)
If inc < 1 Then inc = 1
Do
done = false
For i = lb To ub - inc
' reemplace "<" con ">" para ordenación descendente
If array(i) > array(i + inc) Then
Swap array(i), array(i + inc)
done = true
End If
Next i
Loop Until done = false
Loop Until inc = 1
End Sub
 
Sub quickSort(array() As Double, l As Integer, r As Integer)
Dim As Uinteger size = r - l +1
If size < 2 Then Exit Sub
Dim As Integer i = l, j = r
Dim As Double pivot = array(l + size \ 2)
Do
While array(i) < pivot
i += 1
Wend
While pivot < array(j)
j -= 1
Wend
If i <= j Then
Swap array(i), array(j)
i += 1
j -= 1
End If
Loop Until i > j
If l < j Then quickSort(array(), l, j)
If i < r Then quickSort(array(), i, r)
End Sub
 
Sub rapidSort (array()As Double, inicio As Integer, final As Integer)
Dim As Integer n, wert, nptr, arr, rep
Dim As Integer LoVal = array(inicio), HiVal = array(final)
For n = inicio To final
If LoVal> array(n) Then LoVal = array(n)
If HiVal< array(n) Then HiVal = array(n)
Next
Redim SortArray(LoVal To HiVal) As Double
For n = inicio To final
wert = array(n)
SortArray(wert) += 1
Next
nptr = inicio-1
For arr = LoVal To HiVal
rep = SortArray(arr)
For n = 1 To rep
nptr += 1
array(nptr) = arr
Next
Next
Erase SortArray
End Sub
 
Sub copy_array(s() As Double, d() As Double)
For x As Integer = Lbound(s) To Ubound(s)
d(x) = s(x)
Next
End Sub
 
 
Dim As Integer x, max = 1e5
Dim As Double t1, t2, ran(0 To max), sort(0 To max), rev(0 To max), eq(0 To max)
Dim As String buffer = Space(14)
 
Cls
' fill ran() with random numbers and eq() with same number
For x = 0 To max
ran(x) = Rnd
rev(x) = ran(x) ' make reverse array equal to random array
eq(x) = 1/3
Next x
 
For x = Lbound(rev) To (Ubound(rev) \ 2)
Swap rev(x), rev(Ubound(rev) - x)
Next x
 
Print !"Test times in sec\nArray size ="; max
Print !"\n *Reversed* *Random* *Sorted* *All ones*"
 
sort_1(bubbleSort)
sort_1(exchangeSort)
sort_1(insertionSort)
sort_1(heapSort)
sort_1(shellSort)
sort_2(quickSort)
sort_2(rapidSort)
Sleep</syntaxhighlight>
{{out}}
<pre>Test times in sec
Array size = 100000
 
*Reversed* *Random* *Sorted* *All ones*
bubbleSort 31.645 sec 31.560 sec 12.765 sec 12.754 sec
exchangeSort 12.706 sec 12.708 sec 12.713 sec 12.700 sec
insertionSort 4.724 sec 4.739 sec 0.004 sec 0.004 sec
heapSort 0.028 sec 0.029 sec 0.021 sec 0.002 sec
shellSort 0.049 sec 0.049 sec 0.003 sec 0.003 sec
quickSort 0.013 sec 0.013 sec 0.004 sec 0.005 sec
rapidSort 0.004 sec 0.004 sec 0.004 sec 0.007 sec</pre>
 
 
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<langsyntaxhighlight lang="bbcbasic"> HIMEM = PAGE + 2000000
INSTALL @lib$+"SORTLIB"
INSTALL @lib$+"TIMERLIB"
Line 503 ⟶ 747:
ENDWHILE
a%() += l%
ENDPROC</langsyntaxhighlight>
'''Output:'''
<pre>
Line 547 ⟶ 791:
===Sequence generators===
<tt>csequence.h</tt>
<langsyntaxhighlight lang="c">#ifndef _CSEQUENCE_H
#define _CSEQUENCE_H
#include <stdlib.h>
Line 555 ⟶ 799:
void fillwithrrange(double *v, int n);
void shuffledrange(double *v, int n);
#endif</langsyntaxhighlight>
<tt>csequence.c</tt>
<langsyntaxhighlight lang="c">#include "csequence.h"
 
static double fill_constant;
Line 587 ⟶ 831:
v[r] = t;
}
}</langsyntaxhighlight>
===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>
<langsyntaxhighlight lang="c">#ifndef _WRITETIMINGS_H
#define _WRITETIMINGS_H
#include "sorts.h"
Line 630 ⟶ 874:
};
typedef struct seqdef seqdef_t;
#endif</langsyntaxhighlight>
<tt>writetimings.c</tt>
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
 
Line 735 ⟶ 979:
free(tobesorted);
return 0;
}</langsyntaxhighlight>
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]].
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <math.h>
Line 768 ⟶ 1,012:
 
return 0;
}</langsyntaxhighlight>
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 ⟶ 1,038:
 
=={{header|D}}==
<langsyntaxhighlight lang="d">import std.stdio, std.algorithm, std.container, std.datetime,
std.random, std.typetuple;
 
Line 941 ⟶ 1,185:
nRuns.benchmark!(randomBubble, randomInsertion,
randomHeap, randomBuiltIn).show;
}</langsyntaxhighlight>
{{out}}
<pre>Timings in microseconds:
Line 966 ⟶ 1,210:
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">
<lang Erlang>
-module( compare_sorting_algorithms ).
 
Line 994 ⟶ 1,238:
{Time, _Result} = timer:tc( fun() -> Fun( List_fun(N) ) end ),
{math:log10(N), math:log10(Time)}.
</syntaxhighlight>
</lang>
 
=={{header|Go}}==
{{libheader|gonum/plot}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 1,219 ⟶ 1,463:
ps.Shape = plotutil.DefaultGlyphShapes[dx]
p.Add(pl, ps)
}</langsyntaxhighlight>
{{out}}
[[file:GoComp.png|right|Comparison]]
Line 1,230 ⟶ 1,474:
 
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">import Data.Time.Clock
import Data.List
 
Line 1,259 ⟶ 1,503:
where
step x = (x * a + c) `mod` m
(a, c, m) = (1103515245, 12345, 2^31-1)</langsyntaxhighlight>
 
As a result of testing we get the list of tuples: length of a list and time in microseconds:
Line 1,269 ⟶ 1,513:
Different sorting methods:
 
<langsyntaxhighlight lang="haskell">-- Naive quick sort
qsort :: Ord a => Sorter a
qsort [] = []
Line 1,285 ⟶ 1,529:
-- Insertion sort
isort :: Ord a => Sorter a
isort = foldr insert []</langsyntaxhighlight>
 
Finally, charting routines and the task implementation:
<langsyntaxhighlight lang="haskell">-- chart appears to be logarithmic scale on both axes
barChart :: Char -> [(Int, Time)] -> [String]
barChart ch lst = bar . scale <$> lst
Line 1,326 ⟶ 1,570:
run rand
where
run = comparison [sort, isort, qsort, bsort] "siqb"</langsyntaxhighlight>
 
<pre>λ> main
Line 1,482 ⟶ 1,726:
 
=={{header|J}}==
<syntaxhighlight lang="j">
<lang j>
NB. extracts from other rosetta code projects
ts=: 6!:2, 7!:2@]
Line 1,565 ⟶ 1,809:
(_*pts) + n +./ .*1 0 2|:coef&(p."1) plot x
)
</syntaxhighlight>
</lang>
 
<pre>
Line 1,718 ⟶ 1,962:
 
=={{header|JavaScript}}==
<langsyntaxhighlight lang="javascript">
function swap(a, i, j){
var t = a[i]
Line 1,904 ⟶ 2,148:
 
console.log(sOut)
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,935 ⟶ 2,179:
=={{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.
<langsyntaxhighlight lang="julia">
function comparesorts(tosort)
a = shuffle(["i", "m", "q"])
Line 1,972 ⟶ 2,216:
println("Average sort times for 40000 randomized:")
println("\tinsertion sort:\t$iavg\n\tmerge sort:\t$mavg\n\tquick sort\t$qavg")
</syntaxhighlight>
</lang>
<pre>Average sort times for 40000 ones:
insertion sort: 0.00036058316000000005
Line 1,997 ⟶ 2,241:
 
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.
<langsyntaxhighlight lang="scala">// Version 1.2.31
 
import java.util.Random
Line 2,138 ⟶ 2,382:
println("\n")
}
}</langsyntaxhighlight>
 
{{out}}
Line 2,177 ⟶ 2,421:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Comparing bubble and shell sort:
<langsyntaxhighlight Mathematicalang="mathematica">ClearAll[BubbleSort,ShellSort]
BubbleSort[in_List]:=Module[{x=in,l=Length[in],swapped},swapped=True;
While[swapped,swapped=False;
Line 2,204 ⟶ 2,448:
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"]</langsyntaxhighlight>
{{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 ⟶ 2,459:
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).
 
<langsyntaxhighlight Nimlang="nim">import algorithm
import random
import sequtils
Line 2,367 ⟶ 2,611:
stdout.write &"{time:8d} "
echo ""
echo '\n'</langsyntaxhighlight>
 
{{out}}
Line 2,408 ⟶ 2,652:
=={{header|Phix}}==
{{libheader|Phix/pGUI}}
<!--<langsyntaxhighlight Phixlang="phix">-->
<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 ⟶ 3,009:
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</langsyntaxhighlight>-->
===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 ⟶ 3,026:
{{works with|Python|2.5}}
===Examples of sorting routines===
<langsyntaxhighlight lang="python">def builtinsort(x):
x.sort()
 
Line 2,800 ⟶ 3,044:
if size < 2: return seq
low, middle, up = partition(seq, random.choice(seq))
return qsortranpart(low) + middle + qsortranpart(up)</langsyntaxhighlight>
 
===Sequence generators===
 
<langsyntaxhighlight lang="python">def ones(n):
return [1]*n
 
Line 2,813 ⟶ 3,057:
x = range(n)
random.shuffle(x)
return x</langsyntaxhighlight>
===Write timings===
<langsyntaxhighlight lang="python">def write_timings(npoints=10, maxN=10**4, sort_functions=(builtinsort,insertion_sort, qsort),
sequence_creators = (ones, range, shuffledrange)):
Ns = range(2, maxN, maxN//npoints)
Line 2,821 ⟶ 3,065:
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)</langsyntaxhighlight>
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 ⟶ 3,071:
{{libheader|matplotlib}}
{{libheader|NumPy}}
<langsyntaxhighlight lang="python">import operator
import numpy, pylab
def plotdd(dictplotdict):
Line 2,849 ⟶ 3,093:
pylab.savefig(figname+'.png')
pylab.savefig(figname+'.pdf')
print figname</langsyntaxhighlight>
See [[Plot x, y arrays]] and [[Polynomial Fitting]] subtasks for a basic usage of ''pylab.plot()'' and ''numpy.polyfit()''.
 
<langsyntaxhighlight lang="python">import collections, itertools, glob, re
import numpy
def plot_timings():
Line 2,881 ⟶ 3,125:
# actual plotting
plotdd(df)
plotdd(ds) # see ``plotdd()`` above</langsyntaxhighlight>
 
===Figures: log2( time in microseconds ) vs. log2( sequence length )===
Line 2,887 ⟶ 3,131:
[[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]]
<langsyntaxhighlight lang="python">sort_functions = [
builtinsort, # see implementation above
insertion_sort, # see [[Insertion sort]]
Line 2,904 ⟶ 3,148:
sort_functions=sort_functions,
sequence_creators = (ones, range, shuffledrange))
plot_timings()</langsyntaxhighlight>
Executing above script we get belowed figures.
====ones====
Line 2,927 ⟶ 3,171:
qsort - O(N*log(N))
qsortranpart - O(N) ???
 
=={{header|Raku}}==
{{trans|Julia}}
<syntaxhighlight lang="raku" line># 20221114 Raku programming solution
 
my ($rounds,$size) = 3, 2000;
my @allones = 1 xx $size;
my @sequential = 1 .. $size;
my @randomized = @sequential.roll xx $size;
 
sub insertion_sort ( @a is copy ) { # rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#Raku
for 1 .. @a.end -> \k {
loop (my ($j,\value)=k-1,@a[k];$j>-1&&@a[$j]>value;$j--) {@a[$j+1]=@a[$j]}
@a[$j+1] = value;
}
return @a;
}
 
sub merge_sort ( @a ) { # rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Raku
return @a if @a <= 1;
 
my $m = @a.elems div 2;
my @l = merge_sort @a[ 0 ..^ $m ];
my @r = merge_sort @a[ $m ..^ @a ];
 
return flat @l, @r if @l[*-1] !after @r[0];
return flat gather {
take @l[0] before @r[0] ?? @l.shift !! @r.shift
while @l and @r;
take @l, @r;
}
}
 
sub quick-sort(@data) { # andrewshitov.com/2019/06/23/101-quick-sort-in-perl-6/
return @data if @data.elems <= 1;
 
my ($pivot,@left, @right) = @data[0];
 
for @data[1..*] -> $x { $x < $pivot ?? push @left, $x !! push @right, $x }
 
return flat(quick-sort(@left), $pivot, quick-sort(@right));
}
 
sub comparesorts($rounds, @tosort) {
my ( $iavg, $mavg, $qavg, $t );
 
for (<i m q> xx $rounds).flat.pick(*) -> \sort_type {
given sort_type {
when 'i' { $t = now ; insertion_sort @tosort ; $iavg += now - $t }
when 'm' { $t = now ; merge_sort @tosort ; $mavg += now - $t }
when 'q' { $t = now ; quick-sort @tosort ; $qavg += now - $t }
}
}
return $iavg, $mavg, $qavg »/» $rounds
}
 
for <ones presorted randomized>Z(@allones,@sequential,@randomized) -> ($t,@d) {
say "Average sort times for $size $t:";
{ say "\tinsertion sort\t$_[0]\n\tmerge sort\t$_[1]\n\tquick sort\t$_[2]" }(comparesorts $rounds,@d)
}</syntaxhighlight>
{{out}}
<pre>Average sort times for 2000 ones:
insertion sort 0.112333083
merge sort 0.506624066
quick sort 5.899009606666667
Average sort times for 2000 presorted:
insertion sort 0.03596163
merge sort 0.474839352
quick sort 5.896118350666666
Average sort times for 2000 randomized:
insertion sort 5.352926729
merge sort 0.784896982
quick sort 0.11422247299999999</pre>
 
=={{header|REXX}}==
Line 2,935 ⟶ 3,252:
 
The number of ranges can be increased at the expense of a wider display of output.
<langsyntaxhighlight lang="rexx">/*REXX pgm compares various sorts for 3 types of input sequences: ones/ascending/random.*/
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 ⟶ 3,523:
if i==2 then i= 1
else i= i * 5 % 11
end /*while i¬==0*/; return</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
 
Line 3,232 ⟶ 3,549:
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">class Array
def radix_sort(base=10) # negative value is inapplicable.
ary = dup
Line 3,324 ⟶ 3,641:
puts
end
end</langsyntaxhighlight>
Array#sort is a built-in method.
 
Line 3,362 ⟶ 3,679:
insertion_sort 0.053 5.298 --.--- --.---
bubble_sort 0.206 17.232 --.--- --.---
</pre>
 
=={{header|Sidef}}==
{{trans|Ruby}}
 
''Array#sort'' is a built-in method.
 
<syntaxhighlight lang="ruby">class Array {
method radix_sort(base=10) {
var rounds = ([self.minmax].map{.abs}.max.ilog(base) + 1)
for i in (0..rounds) {
var buckets = (2*base -> of {[]})
var base_i = base**i
for n in self {
var digit = idiv(n, base_i)%base
digit += base if (0 <= n)
buckets[digit].append(n)
}
self = buckets.flat
}
return self
}
 
func merge(left, right) {
var result = []
while (left && right) {
result << [right,left].min_by{.first}.shift
}
result + left + right
}
 
method merge_sort {
var len = self.len
len < 2 && return self
 
var (left, right) = self.part(len>>1)
 
left = left.merge_sort
right = right.merge_sort
 
merge(left, right)
}
 
method quick_sort {
self.len < 2 && return self
var p = self.rand # to avoid the worst cases
var g = self.group_by {|x| x <=> p }
(g{-1} \\ []).quick_sort + (g{0} \\ []) + (g{1} \\ []).quick_sort
}
 
method shell_sort {
var h = self.len
while (h >>= 1) {
range(h, self.end).each { |i|
var k = self[i]
var j
for (j = i; (j >= h) && (k < self[j - h]); j -= h) {
self[j] = self[j - h]
}
self[j] = k
}
}
return self
}
 
method insertion_sort {
{ |i|
var j = i
var k = self[i+1]
while ((j >= 0) && (k < self[j])) {
self[j+1] = self[j]
j--
}
self[j+1] = k
} * self.end
return self
}
 
method bubble_sort {
loop {
var swapped = false
{ |i|
if (self[i] > self[i+1]) {
self[i, i+1] = self[i+1, i]
swapped = true
}
} << ^self.end
swapped || break
}
return self
}
}
 
var data_size = [1e2, 1e3, 1e4, 1e5]
var data = []
data_size.each {|size|
var ary = @(1..size)
data << [size.of(1), ary, ary.shuffle, ary.reverse]
}
 
data = data.transpose
 
var data_type = ["set to all ones", "ascending sequence",
"randomly shuffled", "descending sequence"]
print("Array size: ")
say data_size.map{|size| "%9d" % size}.join
 
data.each_kv {|i, arys|
say "\nData #{data_type[i]}:"
[:sort, :radix_sort, :quick_sort, :merge_sort,
:shell_sort, :insertion_sort, :bubble_sort].each {|m|
printf("%20s ", m)
var timeout = false
arys.each {|ary|
if (!timeout) {
var t0 = Time.micro
ary.clone.(m)
printf(" %7.3f", (var t1 = (Time.micro - t0)))
timeout = true if (t1 > 1.5)
}
else {
print(" --.---")
}
}
say ''
}
}</syntaxhighlight>
{{out}}
<pre>
Array size: 100 1000 10000 100000
 
Data set to all ones:
sort 0.000 0.001 0.011 0.104
radix_sort 0.003 0.026 0.249 2.957
quick_sort 0.004 0.003 0.029 0.298
merge_sort 0.009 0.112 1.269 17.426
shell_sort 0.006 0.164 2.092 --.---
insertion_sort 0.002 0.016 0.149 1.261
bubble_sort 0.001 0.007 0.064 0.647
 
Data ascending sequence:
sort 0.000 0.001 0.011 0.109
radix_sort 0.006 0.063 0.739 9.657
quick_sort 0.006 0.080 0.865 9.578
merge_sort 0.008 0.102 1.178 14.079
shell_sort 0.006 0.091 1.441 16.398
insertion_sort 0.001 0.012 0.124 1.258
bubble_sort 0.001 0.006 0.063 0.628
 
Data randomly shuffled:
sort 0.001 0.009 0.126 1.632
radix_sort 0.006 0.060 0.731 8.768
quick_sort 0.005 0.058 0.742 9.516
merge_sort 0.010 0.132 1.639 --.---
shell_sort 0.010 0.167 2.931 --.---
insertion_sort 0.019 1.989 --.--- --.---
bubble_sort 0.069 7.333 --.--- --.---
 
Data descending sequence:
sort 0.000 0.001 0.012 0.129
radix_sort 0.006 0.061 0.732 8.926
quick_sort 0.005 0.061 0.720 8.712
merge_sort 0.008 0.097 1.148 13.456
shell_sort 0.008 0.133 1.910 --.---
insertion_sort 0.040 3.884 --.--- --.---
bubble_sort 0.092 8.819 --.--- --.---
</pre>
 
Line 3,376 ⟶ 3,859:
{{libheader|Tk}}
{{tcllib|struct::list}}
<langsyntaxhighlight lang="tcl">###############################################################################
# measure and plot times
package require Tk
Line 3,597 ⟶ 4,080:
create_log10_plot "Sorting a '$type' list" size time $sizes $times $algorithms $shapes $colours
}
puts "\ntimes in microseconds, average of $runs runs"</langsyntaxhighlight>
 
{{omit from|GUISS}}
Line 3,646 ⟶ 4,129:
 
Results presented in tabular form as Wren doesn't have a plotting library available at the present time.
<langsyntaxhighlight ecmascriptlang="wren">import "random" for Random
import "./sort" for Sort
import "./fmt" for Fmt
 
var rand = Random.new()
Line 3,768 ⟶ 4,251:
}
System.print("\n")
}</langsyntaxhighlight>
 
{{out}}
Trizen
2,747

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/53740...348774"