Compare sorting algorithms' performance: Difference between revisions

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