Sorting algorithms/Cycle sort: Difference between revisions
Content deleted Content added
add youtube link |
No edit summary |
||
Line 826: | Line 826: | ||
.swap: do p=p while x==@.p; end; parse value @.p x with x @.p;w=w+1;return</lang> |
.swap: do p=p while x==@.p; end; parse value @.p x with x @.p;w=w+1;return</lang> |
||
'''output''' is identical to the 2<sup>nd</sup> version. |
'''output''' is identical to the 2<sup>nd</sup> version. |
||
=={{header|Scala}}== |
|||
Translation of Java version |
|||
<lang scala> |
|||
def cycleSort(a: Array[Int]): (Array[Int], Int) = { |
|||
var writes = 0 |
|||
for (cycleStart <- 0 until a.length - 1) { |
|||
var value = a(cycleStart) |
|||
// count the number of values that are smaller than value since cycleStart |
|||
var pos = cycleStart |
|||
for (i <- cycleStart + 1 until a.length) |
|||
if (a(i) < value) pos += 1 |
|||
// skip if there aren't any |
|||
if (pos != cycleStart) { |
|||
// skip duplicates |
|||
while (a(pos) == value) pos += 1 |
|||
// put val into final position |
|||
val tmp = a(pos) |
|||
a(pos) = value |
|||
value = tmp |
|||
writes += 1 |
|||
// repeat as long as we can find values to swap |
|||
// otherwise start new cycle |
|||
while (pos != cycleStart) { |
|||
pos = cycleStart |
|||
for (i <- cycleStart + 1 until a.length) |
|||
if (a(i) < value) pos += 1 |
|||
while (a(pos) == value) pos += 1 |
|||
val tmp = a(pos) |
|||
a(pos) = value |
|||
value = tmp |
|||
writes += 1 |
|||
} |
|||
} |
|||
} |
|||
(a, writes) |
|||
} |
|||
</lang> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |