Compare sorting algorithms' performance: Difference between revisions
Content added Content deleted
m (→Plot timings) |
(Added Kotlin) |
||
Line 1,457: | Line 1,457: | ||
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. |
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|Kotlin}}== |
|||
This mostly reuses the code from the sorting sub-tasks except that: |
|||
1. All sorting functions have been adjusted where necessary so that they sort an IntArray 'in place'. This ensures that the timings are not affected by time spent copying arrays. |
|||
2. The bubble sort function, which is very slow when sorting 100,000 random numbers, has been optimized somewhat to try and reduce overall execution time, though the program is still taking about 5 minutes to run on my machine. |
|||
Unfortunately the code used to measure CPU time in the 'Time a function' sub-task no longer works properly on my present Windows 10 machine (many results are inexplicably zero). I've therefore had to use the Kotlin library function, measureNanoTime(), instead which measures system time elapsed. Consequently, the results are a bit erratic even when averaged over 10 runs. |
|||
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. |
|||
<lang scala>// Version 1.2.31 |
|||
import java.util.Random |
|||
import kotlin.system.measureNanoTime |
|||
typealias Sorter = (IntArray) -> Unit |
|||
val rand = Random() |
|||
fun onesSeq(n: Int) = IntArray(n) { 1 } |
|||
fun ascendingSeq(n: Int) = shuffledSeq(n).sorted().toIntArray() |
|||
fun shuffledSeq(n: Int) = IntArray(n) { 1 + rand.nextInt(10 * n) } |
|||
fun bubbleSort(a: IntArray) { |
|||
var n = a.size |
|||
do { |
|||
var n2 = 0 |
|||
for (i in 1 until n) { |
|||
if (a[i - 1] > a[i]) { |
|||
val tmp = a[i] |
|||
a[i] = a[i - 1] |
|||
a[i - 1] = tmp |
|||
n2 = i |
|||
} |
|||
} |
|||
n = n2 |
|||
} while (n != 0) |
|||
} |
|||
fun insertionSort(a: IntArray) { |
|||
for (index in 1 until a.size) { |
|||
val value = a[index] |
|||
var subIndex = index - 1 |
|||
while (subIndex >= 0 && a[subIndex] > value) { |
|||
a[subIndex + 1] = a[subIndex] |
|||
subIndex-- |
|||
} |
|||
a[subIndex + 1] = value |
|||
} |
|||
} |
|||
fun quickSort(a: IntArray) { |
|||
fun sorter(first: Int, last: Int) { |
|||
if (last - first < 1) return |
|||
val pivot = a[first + (last - first) / 2] |
|||
var left = first |
|||
var right = last |
|||
while (left <= right) { |
|||
while (a[left] < pivot) left++ |
|||
while (a[right] > pivot) right-- |
|||
if (left <= right) { |
|||
val tmp = a[left] |
|||
a[left] = a[right] |
|||
a[right] = tmp |
|||
left++ |
|||
right-- |
|||
} |
|||
} |
|||
if (first < right) sorter(first, right) |
|||
if (left < last) sorter(left, last) |
|||
} |
|||
sorter(0, a.lastIndex) |
|||
} |
|||
fun radixSort(a: IntArray) { |
|||
val tmp = IntArray(a.size) |
|||
for (shift in 31 downTo 0) { |
|||
tmp.fill(0) |
|||
var j = 0 |
|||
for (i in 0 until a.size) { |
|||
val move = (a[i] shl shift) >= 0 |
|||
val toBeMoved = if (shift == 0) !move else move |
|||
if (toBeMoved) |
|||
tmp[j++] = a[i] |
|||
else { |
|||
a[i - j] = a[i] |
|||
} |
|||
} |
|||
for (i in j until tmp.size) tmp[i] = a[i - j] |
|||
for (i in 0 until a.size) a[i] = tmp[i] |
|||
} |
|||
} |
|||
val gaps = listOf(701, 301, 132, 57, 23, 10, 4, 1) // Marcin Ciura's gap sequence |
|||
fun shellSort(a: IntArray) { |
|||
for (gap in gaps) { |
|||
for (i in gap until a.size) { |
|||
val temp = a[i] |
|||
var j = i |
|||
while (j >= gap && a[j - gap] > temp) { |
|||
a[j] = a[j - gap] |
|||
j -= gap |
|||
} |
|||
a[j] = temp |
|||
} |
|||
} |
|||
} |
|||
fun main(args: Array<String>) { |
|||
val runs = 10 |
|||
val lengths = listOf(1, 10, 100, 1_000, 10_000, 100_000) |
|||
val sorts = listOf<Sorter>( |
|||
::bubbleSort, ::insertionSort, ::quickSort, ::radixSort, ::shellSort |
|||
) |
|||
/* allow JVM to compile sort functions before timings start */ |
|||
for (sort in sorts) sort(intArrayOf(1)) |
|||
val sortTitles = listOf("Bubble", "Insert", "Quick ", "Radix ", "Shell ") |
|||
val seqTitles = listOf("All Ones", "Ascending", "Shuffled") |
|||
val totals = List(seqTitles.size) { List(sorts.size) { LongArray(lengths.size) } } |
|||
for ((k, n) in lengths.withIndex()) { |
|||
val seqs = listOf(onesSeq(n), ascendingSeq(n), shuffledSeq(n)) |
|||
repeat(runs) { |
|||
for (i in 0 until seqs.size) { |
|||
for (j in 0 until sorts.size) { |
|||
val seq = seqs[i].copyOf() |
|||
totals[i][j][k] += measureNanoTime { sorts[j](seq) } |
|||
} |
|||
} |
|||
} |
|||
} |
|||
println("All timings in micro-seconds\n") |
|||
print("Sequence length") |
|||
for (len in lengths) print("%8d ".format(len)) |
|||
println("\n") |
|||
for (i in 0 until seqTitles.size) { |
|||
println(" ${seqTitles[i]}:") |
|||
for (j in 0 until sorts.size) { |
|||
print(" ${sortTitles[j]} ") |
|||
for (k in 0 until lengths.size) { |
|||
val time = totals[i][j][k] / runs / 1_000 |
|||
print("%8d ".format(time)) |
|||
} |
|||
println() |
|||
} |
|||
println("\n") |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
All timings in micro-seconds |
|||
Sequence length 1 10 100 1000 10000 100000 |
|||
All Ones: |
|||
Bubble 1 2 6 24 26 264 |
|||
Insert 1 16 10 14 48 518 |
|||
Quick 2 7 18 46 397 5181 |
|||
Radix 38 79 501 3720 864 9096 |
|||
Shell 11 15 43 189 407 4105 |
|||
Ascending: |
|||
Bubble 1 2 6 8 24 270 |
|||
Insert 0 2 9 14 47 496 |
|||
Quick 1 6 19 33 282 3347 |
|||
Radix 38 71 264 415 1869 21403 |
|||
Shell 7 10 42 171 399 4052 |
|||
Shuffled: |
|||
Bubble 1 5 436 3292 275224 27730705 |
|||
Insert 0 3 176 754 24759 2546180 |
|||
Quick 1 7 24 106 1281 14982 |
|||
Radix 28 73 622 317 1891 21617 |
|||
Shell 11 19 88 408 1946 36980 |
|||
</pre> |
|||
===Conclusions=== |
|||
As expected quick sort is faster than the other methods when applied to random data of a reasonable size though radix and shell sort are also respectable performers for large amounts of random data. In contrast, bubble and insertion sorts are orders of magnitude slower, particularly the former. |
|||
On the other hand, bubble and insertion sorts are much quicker than the other methods for constant data and for data which is already sorted in an ascending direction, bubble sort being the faster of the two. |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |