Compare sorting algorithms' performance: Difference between revisions
Compare sorting algorithms' performance (view source)
Revision as of 16:00, 15 December 2023
, 5 months agoAdded Sidef
m (added sorting category.) |
(Added Sidef) |
||
| (12 intermediate revisions by 7 users not shown) | |||
Line 34:
=={{header|AutoHotkey}}==
{{in progress|lang=AutoHotkey|day=16|month=1|year=2010}}
<
#Persistent
Line 337:
Sort, var, N D`,
Return var
}</
=={{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}}
<
INSTALL @lib$+"SORTLIB"
INSTALL @lib$+"TIMERLIB"
Line 503 ⟶ 747:
ENDWHILE
a%() += l%
ENDPROC</
'''Output:'''
<pre>
Line 547 ⟶ 791:
===Sequence generators===
<tt>csequence.h</tt>
<
#define _CSEQUENCE_H
#include <stdlib.h>
Line 555 ⟶ 799:
void fillwithrrange(double *v, int n);
void shuffledrange(double *v, int n);
#endif</
<tt>csequence.c</tt>
<
static double fill_constant;
Line 587 ⟶ 831:
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 ⟶ 874:
};
typedef struct seqdef seqdef_t;
#endif</
<tt>writetimings.c</tt>
<
#include <stdlib.h>
Line 735 ⟶ 979:
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 ⟶ 1,012:
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 ⟶ 1,038:
=={{header|D}}==
<
std.random, std.typetuple;
Line 941 ⟶ 1,185:
nRuns.benchmark!(randomBubble, randomInsertion,
randomHeap, randomBuiltIn).show;
}</
{{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">
-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>
=={{header|Go}}==
{{libheader|gonum/plot}}
<
import (
Line 1,219 ⟶ 1,463:
ps.Shape = plotutil.DefaultGlyphShapes[dx]
p.Add(pl, ps)
}</
{{out}}
[[file:GoComp.png|right|Comparison]]
Line 1,228 ⟶ 1,472:
On random data (triangles) insertion and bubble sort show worse performance than quicksort.
<br clear=all>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import Data.Time.Clock
import Data.List
type Time = Integer
type Sorter a = [a] -> [a]
-- Simple timing function (in microseconds)
timed :: IO a -> IO (a, Time)
timed prog = do
t0 <- getCurrentTime
x <- prog
t1 <- x `seq` getCurrentTime
return (x, ceiling $ 1000000 * diffUTCTime t1 t0)
-- testing sorting algorithm on a given set
test :: [a] -> Sorter a -> IO [(Int, Time)]
test set srt = mapM (timed . run) ns
where
ns = take 15 $ iterate (\x -> (x * 5) `div` 3) 10
run n = pure $ length $ srt (take n set)
-- sample sets
constant = repeat 1
presorted = [1..]
random = (`mod` 100) <$> iterate step 42
where
step x = (x * a + c) `mod` m
(a, c, m) = (1103515245, 12345, 2^31-1)</syntaxhighlight>
As a result of testing we get the list of tuples: length of a list and time in microseconds:
<pre>λ> test ones sort
[(10,9),(16,7),(26,5),(43,5),(71,6),(118,8),(196,12),(326,18),(543,28),(905,41),(1508,68),(2513,108),(4188,191),(6980,303),(11633,484)]
λ> test rand sort
[(10,8),(16,7),(26,7),(43,9),(71,15),(118,24),(196,43),(326,82),(543,136),(905,270),(1508,482),(2513,1004),(4188,1926),(6980,4612),(11633,7286)]</pre>
Different sorting methods:
<syntaxhighlight lang="haskell">-- Naive quick sort
qsort :: Ord a => Sorter a
qsort [] = []
qsort (h:t) = qsort (filter (< h) t) ++ [h] ++ qsort (filter (>= h) t)
-- Bubble sort
bsort :: Ord a => Sorter a
bsort s = case _bsort s of
t | t == s -> t
| otherwise -> bsort t
where _bsort (x:x2:xs) | x > x2 = x2:_bsort (x:xs)
| otherwise = x :_bsort (x2:xs)
_bsort s = s
-- Insertion sort
isort :: Ord a => Sorter a
isort = foldr insert []</syntaxhighlight>
Finally, charting routines and the task implementation:
<syntaxhighlight lang="haskell">-- chart appears to be logarithmic scale on both axes
barChart :: Char -> [(Int, Time)] -> [String]
barChart ch lst = bar . scale <$> lst
where
scale (x,y) = (x, round $ (3*) $ log $ fromIntegral y)
bar (x,y) = show x ++ "\t" ++ replicate y ' ' ++ [ch]
over :: String -> String -> String
over s1 s2 = take n $ zipWith f (pad s1) (pad s2)
where
f ' ' c = c
f c ' ' = c
f y _ = y
pad = (++ repeat ' ')
n = length s1 `max` length s2
comparison :: Ord a => [Sorter a] -> [Char] -> [a] -> IO ()
comparison sortings chars set = do
results <- mapM (test set) sortings
let charts = zipWith barChart chars results
putStrLn $ replicate 50 '-'
mapM_ putStrLn $ foldl1 (zipWith over) charts
putStrLn $ replicate 50 '-'
let times = map (fromInteger . snd) <$> results
let ratios = mean . zipWith (flip (/)) (head times) <$> times
putStrLn "Comparing average time ratios:"
mapM_ putStrLn $ zipWith (\r s -> [s] ++ ": " ++ show r) ratios chars
where
mean lst = sum lst / genericLength lst
main = do
putStrLn "comparing on list of ones"
run ones
putStrLn "\ncomparing on presorted list"
run seqn
putStrLn "\ncomparing on shuffled list"
run rand
where
run = comparison [sort, isort, qsort, bsort] "siqb"</syntaxhighlight>
<pre>λ> main
comparing on list of ones
--------------------------------------------------
10 is b q
16 is b q
26 s b q
43 si b q
71 si b q
118 si b q
196 si b q
326 si b q
543 s i b q
905 s i b q
1508 s i b q
2513 s i b q
4188 s i b q
6980 s i b q
11633 s i b q
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 1.9768226698141058
q: 4948.447011286744
b: 8.648711819912956
comparing on presorted list
--------------------------------------------------
10 isb q
16 s b q
26 s b q
43 i s b q
71 is b q
118 s b q
196 s b q
326 si b q
543 si b q
905 si b q
1508 si b q
2513 si b q
4188 s i b q
6980 s i b q
11633 s i b q
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 1.2828547504398033
q: 2586.058542372048
b: 4.478306385307422
comparing on shuffled list
--------------------------------------------------
10 i qs
16 is q b
26 s q b
43 is q b
71 s q b
118 si q b
196 si q b
326 s i b
543 s qi b
905 s i b
1508 s q i b
2513 s q i b
4188 s q i b
6980 s q i b
11633 s q i b
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 33.0167854766955
q: 4.778965210071694
b: 920.9348663725772</pre>
We see that well known Haskell meme -- naive quicksort, is total mess on degenerate cases, and it does much better in general, still being significantly more slow then standard implementation. This tests were done in GHCi. Lazy Haskell program may be drastically rewritten and optimized during compilation. Let's see how it goes after compilation:
<pre>$ ghc -O2 CompareSort.hs
[1 of 1] Compiling Main ( CompareSort.hs, CompareSort.o )
Linking CompareSort ...
$ ./CompareSort
comparing on list of ones
--------------------------------------------------
10 i q s
16 s q
26 i s q
43 bs i q
71 ibs q
118 ibs q
196 ib s q
326 i bs q
543 bis q
905 i bs q
1508 ib s q
2513 ibs q
4188 ib s q
6980 si q
11633 si q
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 0.9148588587463226
q: 751.3527462449417
b: 0.774109602468018
comparing on presorted list
--------------------------------------------------
10 i s
16 s q
26 s q
43 i s q
71 s q
118 sb q
196 is q
326 isb q
543 sb q
905 sb i q
1508 is q
2513 sb q
4188 is q
6980 ibs q
11633 s q
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 1.114052564981571
q: 577.8734457264803
b: 1.1171025867573912
comparing on shuffled list
--------------------------------------------------
10 iqs
16 is
26 isb
43 sq b
71 si b
118 si b
196 s i b
326 sq i b
543 s i b
905 sq i b
1508 s q i b
2513 s q i b
4188 s q i b
6980 s q i b
11633 s q i b
--------------------------------------------------
Comparing average time ratios:
s: 1.0
i: 29.346876854773274
q: 1.3750763918038253
b: 71.47503300525689</pre>
Even though quicksort still sucks on degenerate lists, it does really much better when compiled. Bubble sort had also improved it's rate, in contrast to insertion sort which didn't gain anything from compilation.
=={{header|J}}==
<syntaxhighlight lang="j">
NB. extracts from other rosetta code projects
ts=: 6!:2, 7!:2@]
Line 1,313 ⟶ 1,809:
(_*pts) + n +./ .*1 0 2|:coef&(p."1) plot x
)
</syntaxhighlight>
<pre>
Line 1,465 ⟶ 1,961:
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|JavaScript}}==
<syntaxhighlight lang="javascript">
function swap(a, i, j){
var t = a[i]
a[i] = a[j]
a[j] = t
}
// Heap Sort
function heap_sort(a){
var n = a.length
function heapify(i){
var t = a[i]
while (true){
var l = 2 * i + 1, r = l + 1
var m = r < n ? (a[l] > a[r] ? l : r) : (l < n ? l : i)
if (m != i && a[m] > t){
a[i] = a[m]
i = m
}
else{
break
}
}
a[i] = t;
}
for (let i = Math.floor(n / 2) - 1; i >= 0; i--){
heapify(i)
}
for (let i = n - 1; i >= 1; i--){
swap(a, 0, i)
n--
heapify(0)
}
}
// Merge Sort
function merge_sort(a){
var b = new Array(a.length)
function rec(l, r){
if (l < r){
var m = Math.floor((l + r) / 2)
rec(l, m)
rec(m + 1, r)
var i = l, j = m + 1, k = 0;
while (i <= m && j <= r) b[k++] = (a[i] > a[j] ? a[j++] : a[i++])
while (j <= r) b[k++] = a[j++]
while (i <= m) b[k++] = a[i++]
for (k = l; k <= r; k++){
a[k] = b[k - l]
}
}
}
rec(0, a.length-1)
}
// Quick Sort
function quick_sort(a){
function rec(l, r){
if (l < r){
var p = a[l + Math.floor((r - l + 1)*Math.random())]
var i = l, j = l, k = r
while (j <= k){
if (a[j] < p){
swap(a, i++, j++)
}
else if (a[j] > p){
swap(a, j, k--)
}
else{
j++
}
}
rec(l, i - 1)
rec(k + 1, r)
}
}
rec(0, a.length - 1)
}
// Shell Sort
function shell_sort(a){
var n = a.length
var gaps = [100894, 44842, 19930, 8858, 3937, 1750, 701, 301, 132, 57, 23, 10, 4, 1]
for (let x of gaps){
for (let i = x; i < n; i++){
var t = a[i], j;
for (j = i; j >= x && a[j - x] > t; j -= x){
a[j] = a[j - x];
}
a[j] = t;
}
}
}
// Comb Sort (+ Insertion sort optimization)
function comb_sort(a){
var n = a.length
for (let x = n; x >= 10; x = Math.floor(x / 1.3)){
for (let i = 0; i + x < n; i++){
if (a[i] > a[i + x]){
swap(a, i, i + x)
}
}
}
for (let i = 1; i < n; i++){
var t = a[i], j;
for (j = i; j > 0 && a[j - 1] > t; j--){
a[j] = a[j - 1]
}
a[j] = t;
}
}
// Test
function test(f, g, e){
var res = ""
for (let n of e){
var a = new Array(n)
var s = 0
for (let k = 0; k < 10; k++){
for (let i = 0; i < n; i++){
a[i] = g(i)
}
var start = Date.now()
f(a)
s += Date.now() - start
}
res += Math.round(s / 10) + "\t"
}
return res
}
// Main
var e = [5000, 10000, 100000, 500000, 1000000, 2000000]
var sOut = "Test times in ms\n\nElements\t" + e.join("\t") + "\n\n"
sOut += "*All ones*\n"
sOut += "heap_sort\t" + test(heap_sort, (x => 1), e) + "\n"
sOut += "quick_sort\t" + test(quick_sort, (x => 1), e) + "\n"
sOut += "merge_sort\t" + test(merge_sort, (x => 1), e) + "\n"
sOut += "shell_sort\t" + test(shell_sort, (x => 1), e) + "\n"
sOut += "comb_sort\t" + test(comb_sort, (x => 1), e) + "\n\n"
sOut += "*Sorted*\n"
sOut += "heap_sort\t" + test(heap_sort, (x => x), e) + "\n"
sOut += "quick_sort\t" + test(quick_sort, (x => x), e) + "\n"
sOut += "merge_sort\t" + test(merge_sort, (x => x), e) + "\n"
sOut += "shell_sort\t" + test(shell_sort, (x => x), e) + "\n"
sOut += "comb_sort\t" + test(comb_sort, (x => x), e) + "\n\n"
sOut += "*Random*\n"
sOut += "heap_sort\t" + test(heap_sort, (x => Math.random()), e) + "\n"
sOut += "quick_sort\t" + test(quick_sort, (x => Math.random()), e) + "\n"
sOut += "merge_sort\t" + test(merge_sort, (x => Math.random()), e) + "\n"
sOut += "shell_sort\t" + test(shell_sort, (x => Math.random()), e) + "\n"
sOut += "comb_sort\t" + test(comb_sort, (x => Math.random()), e) + "\n"
console.log(sOut)
</syntaxhighlight>
{{out}}
<pre>
Test times in ms
Elements 5000 10000 100000 500000 1000000 2000000
*All ones*
heap_sort 0 0 0 3 5 11
quick_sort 0 0 0 1 2 4
merge_sort 1 1 9 50 103 216
shell_sort 1 0 4 19 39 78
comb_sort 1 0 6 35 75 160
*Sorted*
heap_sort 1 1 7 38 79 162
quick_sort 1 1 10 54 111 230
merge_sort 1 1 9 50 103 217
shell_sort 0 0 3 19 39 78
comb_sort 0 1 6 34 75 160
*Random*
heap_sort 1 1 12 71 161 383
quick_sort 1 1 15 85 177 373
merge_sort 1 1 18 103 215 451
shell_sort 1 1 15 89 188 397
comb_sort 1 1 12 74 159 343
</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"])
Line 1,505 ⟶ 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>
<pre>Average sort times for 40000 ones:
insertion sort: 0.00036058316000000005
Line 1,530 ⟶ 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.
<
import java.util.Random
Line 1,671 ⟶ 2,382:
println("\n")
}
}</
{{out}}
Line 1,710 ⟶ 2,421:
=={{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 1,737 ⟶ 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"]</
{{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 1,748 ⟶ 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).
<
import random
import sequtils
Line 1,900 ⟶ 2,611:
stdout.write &"{time:8d} "
echo ""
echo '\n'</
{{out}}
Line 1,941 ⟶ 2,652:
=={{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,298 ⟶ 3,009:
<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,315 ⟶ 3,026:
{{works with|Python|2.5}}
===Examples of sorting routines===
<
x.sort()
Line 2,333 ⟶ 3,044:
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,346 ⟶ 3,057:
x = range(n)
random.shuffle(x)
return x</
===Write timings===
<
sequence_creators = (ones, range, shuffledrange)):
Ns = range(2, maxN, maxN//npoints)
Line 2,354 ⟶ 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)</
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,360 ⟶ 3,071:
{{libheader|matplotlib}}
{{libheader|NumPy}}
<
import numpy, pylab
def plotdd(dictplotdict):
Line 2,382 ⟶ 3,093:
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,414 ⟶ 3,125:
# actual plotting
plotdd(df)
plotdd(ds) # see ``plotdd()`` above</
===Figures: log2( time in microseconds ) vs. log2( sequence length )===
Line 2,420 ⟶ 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]]
<
builtinsort, # see implementation above
insertion_sort, # see [[Insertion sort]]
Line 2,437 ⟶ 3,148:
sort_functions=sort_functions,
sequence_creators = (ones, range, shuffledrange))
plot_timings()</
Executing above script we get belowed figures.
====ones====
Line 2,460 ⟶ 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}}==
One goal for this REXX program was to include as many different sorts (that sorted arrays and not lists).
Because of the disparencies of some sorting algorithms, the range of numbers was chosen to be '''5''' so that the
<br>slower sorts wouldn't consume a lot of time trying to sort larger arrays.
The number of ranges can be increased at the expense of a wider display of output.
<syntaxhighlight 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.*/
if start#=='' | start#=="," then start#= 250 /* " " " " " " */
if seed=='' | seed=="," then seed= 1946 /*use a repeatable seed for RANDOM BIF*/
if datatype(seed, 'W') then call random ,,seed /*Specified? Then use as a RANDOM seed*/
kinds= 3;
do ra=1 for ranges
hdr= hdr || center( commas(#) "numbers", 25)'│' /*(top) header for the output title.*/
do ki=1 for kinds
Line 2,475 ⟶ 3,267:
call set@; call time 'R'; call cocktailSB #; cocktailSB.ra.ki= format(time("E"),,2)
call set@; call time 'R'; call comb #; comb.ra.ki= format(time("E"),,2)
call set@; call time 'R'; call exchange #; exchange.ra.ki= format(time("E"),,2)
call set@; call time 'R'; call gnome #; gnome.ra.ki= format(time("E"),,2)
call set@; call time 'R'; call heap #; heap.ra.ki= format(time("E"),,2)
Line 2,495 ⟶ 3,288:
xcreps= copies( left('', Lr-1, '─')"┼", ranges)
say center('' , 12, '─')"┼"left(xcreps, length(xcreps)-1)"┤"
call show 'bubble' /*
call show 'cocktail' /*
call show 'cocktailSB' /*+Shifting Bounds*/ /*
call show 'comb' /*
call show '
call show '
call show '
call show '
call show '
call show '
call show '
call show '
call show '
call show 'shell' /* ◄──── " " " shell " */
say translate(center('' , 12, '─')"┴"left(xcreps, length(xcreps)-1)"┘", '┴', "┼")
exit 0 /*stick a fork in it, we're all done. */
Line 2,572 ⟶ 3,366:
end /*j*/ /* [↑] swap two elements in the array.*/
end /*until*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
exchange: procedure expose @.; parse arg n 1 h /*both N and H have the array size.*/
do while h>1; h= h % 2
do i=1 for n-h; j= i; k= h+i
do while @.k<@.j
_= @.j; @.j= @.k; @.k= _; if h>=j then leave; j= j-h; k= k-h
end /*while @.k<@.j*/
end /*i*/
end /*while h>1*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
gnome: procedure expose @.; parse arg n; k= 2 /*N: is number items. */
Line 2,709 ⟶ 3,512:
end /*j*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
shell: procedure expose @.; parse arg N /*obtain the N from the argument list*/
i= N % 2 /*% is integer division in REXX. */
do while i\==0
do j=i+1 to N; k= j; p= k-i /*P: previous item*/
_= @.j
do while k>=i+1 & @.p>_; @.k= @.p; k= k-i; p= k-i
end /*while k≥i+1*/
@.k= _
end /*j*/
if i==2 then i= 1
else i= i * 5 % 11
end
{{out|output|text= when using the default inputs:}}
(Shown at
<pre style="font-size:
│ 250 numbers │ 500 numbers │ 1,000 numbers │ 2,000 numbers │ 4,000 numbers │
sort type │ allONES ascend random │ allONES ascend random │ allONES ascend random │ allONES ascend random │ allONES ascend random │
────────────┼─────────────────────────┼─────────────────────────┼─────────────────────────┼─────────────────────────┼─────────────────────────┤
bubble │ 0.00 0.00 0.06 │ 0.
cocktail │ 0.00 0.00 0.08 │ 0.00 0.02 0.27 │ 0.00 0.
cocktailSB │ 0.00 0.00 0.05 │ 0.
comb │ 0.
shell │ 0.02 0.00 0.00 │ 0.00 0.00 0.02 │ 0.02 0.02 0.05 │ 0.05 0.05 0.09 │ 0.13 0.11 0.22 │
────────────┴─────────────────────────┴─────────────────────────┴─────────────────────────┴─────────────────────────┴─────────────────────────┘
</pre>
=={{header|Ruby}}==
<
def radix_sort(base=10) # negative value is inapplicable.
ary = dup
Line 2,842 ⟶ 3,641:
puts
end
end</
Array#sort is a built-in method.
Line 2,880 ⟶ 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 2,894 ⟶ 3,859:
{{libheader|Tk}}
{{tcllib|struct::list}}
<
# measure and plot times
package require Tk
Line 3,115 ⟶ 4,080:
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,164 ⟶ 4,129:
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
var rand = Random.new()
Line 3,286 ⟶ 4,251:
}
System.print("\n")
}</
{{out}}
| |||