Sorting algorithms/Cycle sort: Difference between revisions
Added Kotlin
(Added FreeBASIC) |
(Added Kotlin) |
||
Line 748:
[0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 5, 5, 6, 8, 9]
writes: 14</pre>
=={{header|Kotlin}}==
Translation of the algorithm in the Wikipedia article:
<lang scala>// version 1.1.0
/** Sort an array in place and return the number of writes */
fun <T: Comparable<T>> cycleSort(array: Array<T>): Int {
var writes = 0
// Loop through the array to find cycles to rotate.
for (cycleStart in 0 until array.size - 1) {
var item = array[cycleStart]
// Find where to put the item.
var pos = cycleStart
for (i in cycleStart + 1 until array.size) if (array[i] < item) pos++
// If the item is already there, this is not a cycle.
if (pos == cycleStart) continue
// Otherwise, put the item there or right after any duplicates.
while (item == array[pos]) pos++
var temp = array[pos]
array[pos] = item
item = temp
writes++
// Rotate the rest of the cycle.
while (pos != cycleStart) {
// Find where to put the item.
pos = cycleStart
for (i in cycleStart + 1 until array.size) if (array[i] < item) pos++
// Otherwise, put the item there or right after any duplicates.
while (item == array[pos]) pos++
var temp2 = array[pos]
array[pos] = item
item = temp2
writes++
}
}
return writes
}
fun <T: Comparable<T>> printResults(array: Array<T>) {
println(array.asList())
val writes = cycleSort(array)
println("After sorting with $writes writes:")
println(array.asList())
println()
}
fun main(args: Array<String>) {
val array = arrayOf(0, 1, 2, 2, 2, 2, 1, 9, 3, 5, 5, 8, 4, 7, 0, 6)
printResults(array)
val array2 = arrayOf(5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1)
printResults(array2)
val array3 = "the quick brown fox jumps over the lazy dog".split(' ').toTypedArray()
printResults(array3)
val array4 = "sphinx of black quartz judge my vow".replace(" ", "").toCharArray().distinct().toTypedArray()
printResults(array4)
}</lang>
{{out}}
<pre>
[0, 1, 2, 2, 2, 2, 1, 9, 3, 5, 5, 8, 4, 7, 0, 6]
After sorting with 10 writes:
[0, 0, 1, 1, 2, 2, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9]
[5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1]
After sorting with 14 writes:
[0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 5, 5, 6, 8, 9]
[the, quick, brown, fox, jumps, over, the, lazy, dog]
After sorting with 8 writes:
[brown, dog, fox, jumps, lazy, over, quick, the, the]
[s, p, h, i, n, x, o, f, b, l, a, c, k, q, u, r, t, z, j, d, g, e, m, y, v, w]
After sorting with 26 writes:
[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z]
</pre>
=={{header|NetRexx}}==
| |||