Compare sorting algorithms' performance: Difference between revisions
Compare sorting algorithms' performance (view source)
Revision as of 16:23, 4 May 2021
, 3 years agoAdded Wren
m (→{{header|Phix}}: added syntax colouring the hard way) |
(Added Wren) |
||
Line 2,822:
[[Image:Tcl_sort_reversed.png]]
[[Image:Tcl_sort_random.png]]
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-sort}}
{{libheader|Wren-fmt}}
The quick, insertion and shell sorts all use the 'in place' implementations in the Wren-sort module.
The radix sort is lifted from the task of that name and, although more complicated, appears to be much faster than the Kotlin version.
For the bubble sort, I have used the optimized Kotlin implementation.
I've limited the size of the arrays to 50,000 though even then the program takes the best part of half an hour to run, due to the extreme slowness of the bubble and insertion sorts for large amounts of shuffled data.
Results presented in tabular form as Wren doesn't have a plotting library available at the present time.
<lang ecmascript>import "random" for Random
import "/sort" for Sort
import "/fmt" for Fmt
var rand = Random.new()
var onesSeq = Fn.new { |n| List.filled(n, 1) }
var shuffledSeq = Fn.new { |n|
var seq = List.filled(n, 0)
for (i in 0...n) seq[i] = 1 + rand.int(10 * n)
return seq
}
var ascendingSeq = Fn.new { |n|
var seq = shuffledSeq.call(n)
seq.sort()
return seq
}
var bubbleSort = Fn.new { |a|
var n = a.count
while (true) {
var n2 = 0
for (i in 1...n) {
if (a[i - 1] > a[i]) {
a.swap(i, i - 1)
n2 = i
}
}
n = n2
if (n == 0) break
}
}
// counting sort of 'a' according to the digit represented by 'exp'
var countSort = Fn.new { |a, exp|
var n = a.count
var output = [0] * n
var count = [0] * 10
for (i in 0...n) {
var t = (a[i]/exp).truncate % 10
count[t] = count[t] + 1
}
for (i in 1..9) count[i] = count[i] + count[i-1]
for (i in n-1..0) {
var t = (a[i]/exp).truncate % 10
output[count[t] - 1] = a[i]
count[t] = count[t] - 1
}
for (i in 0...n) a[i] = output[i]
}
// sorts 'a' in place
var radixSort = Fn.new { |a|
// check for negative elements
var min = a.reduce { |m, i| (i < m) ? i : m }
// if there are any, increase all elements by -min
if (min < 0) (0...a.count).each { |i| a[i] = a[i] - min }
// now get the maximum to know number of digits
var max = a.reduce { |m, i| (i > m) ? i : m }
// do counting sort for each digit
var exp = 1
while ((max/exp).truncate > 0) {
countSort.call(a, exp)
exp = exp * 10
}
// if there were negative elements, reduce all elements by -min
if (min < 0) (0...a.count).each { |i| a[i] = a[i] + min }
}
var measureTime = Fn.new { |sort, seq|
var start = System.clock
sort.call(seq)
return ((System.clock - start) * 1e6).round // microseconds
}
var runs = 10
var lengths = [1, 10, 100, 1000, 10000, 50000]
var sorts = [
bubbleSort,
Fn.new { |a| Sort.insertion(a) },
Fn.new { |a| Sort.quick(a) },
radixSort,
Fn.new { |a| Sort.shell(a) }
]
var sortTitles = ["Bubble", "Insert", "Quick ", "Radix ", "Shell "]
var seqTitles = ["All Ones", "Ascending", "Shuffled"]
var totals = List.filled(seqTitles.count, null)
for (i in 0...totals.count) {
totals[i] = List.filled(sorts.count, null)
for (j in 0...sorts.count) totals[i][j] = List.filled(lengths.count, 0)
}
var k = 0
for (n in lengths) {
var seqs = [onesSeq.call(n), ascendingSeq.call(n), shuffledSeq.call(n)]
for (r in 0...runs) {
for (i in 0...seqs.count) {
for (j in 0...sorts.count) {
var seq = seqs[i].toList
totals[i][j][k] = totals[i][j][k] + measureTime.call(sorts[j], seq)
}
}
}
k = k + 1
}
System.print("All timings in microseconds\n")
System.write("Sequence length")
for (len in lengths) Fmt.write("$8d ", len)
System.print("\n")
for (i in 0...seqTitles.count) {
System.print(" %(seqTitles[i]):")
for (j in 0...sorts.count) {
System.write(" %(sortTitles[j]) ")
for (k in 0...lengths.count) {
var time = (totals[i][j][k] / runs).round
Fmt.write("$8d ", time)
}
System.print()
}
System.print("\n")
}</lang>
{{out}}
<pre>
All timings in microseconds
Sequence length 1 10 100 1000 10000 50000
All Ones:
Bubble 1 2 9 61 643 3225
Insert 1 3 16 118 1256 6338
Quick 1 8 92 983 14746 87660
Radix 6 13 62 460 4823 24379
Shell 1 5 59 770 9542 48873
Ascending:
Bubble 1 2 8 61 637 3221
Insert 1 3 16 118 1251 6371
Quick 1 7 65 643 9149 54199
Radix 7 23 169 1648 21428 130609
Shell 1 5 60 779 9537 49041
Shuffled:
Bubble 1 7 451 37271 4025966 99834073
Insert 0 7 295 24040 2597162 64875212
Quick 1 8 101 1149 16256 95590
Radix 5 24 163 1688 22443 136228
Shell 1 8 111 1514 25180 230897
</pre>
The results are much the same as one might have expected beforehand.
As far as the shuffled data is concerned, quick sort is the fastest though radix and shell sorts are also reasonable performers. Bubble and insertion sorts are very slow indeed for large amounts of data.
Conversely, if the data is already sorted into ascending order, bubble and insertion sorts are much faster than the others and radix sort is the slowest.
If all data is the same, a similar pattern emerges except that radix sort performs better than both shell and quick sorts, the latter being the slowest.
| |||