Sorting algorithms/Cycle sort: Difference between revisions

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