Sorting algorithms/Cycle sort: Difference between revisions
→{{header|jq}}
Drkameleon (talk | contribs) (Added Arturo implementation) |
|||
Line 979:
[0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 5, 5, 6, 8, 9]
writes: 14</pre>
=={{header|jq}}==
{{trans|Wren}}
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
The following implementation is based on the [[#Wren|Wren]] entry except for the
use of `swap`, which exposes a bug in the Wren version (as of 2021.09.12) regarding `writes`.
<lang jq>
# Output: {a: sortedInput, write: numberOfSwaps}
def cycleSort:
def swap(f;g): g as $t | g = f | f = $t | .writes += 1;
{ a: ., writes: 0, len: length }
| reduce range(0; .len - 1) as $cs (.;
.item = .a[$cs]
| .pos = $cs
| reduce range($cs+1; .len) as $i (.;
if .a[$i] < .item then .pos += 1 else . end )
| if .pos != $cs
then until (.item != .a[.pos]; .pos += 1)
| swap(.a[.pos]; .item)
| until (.pos == $cs;
.pos = $cs
| reduce range($cs+1; .len) as $i (.;
if .a[$i] < .item then .pos += 1 else . end)
| until (.item != .a[.pos]; .pos += 1)
| swap(.a[.pos]; .item) )
else .
end )
| {a, writes} ;</lang>
'''The Task'''
<lang jq>[0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6],
[4, 65, 2, -31, 0, 99, 2, 83, 782, 1],
[7, 5, 2, 6, 1, 4, 2, 6, 3]
| "Before : \(.)",
(cycleSort
| "After : \(.a)",
"Writes : \(.writes)",
"")</lang>
{{out}}
<pre>
Before : [0,1,2,2,2,2,1,9,3.5,5,8,4,7,0,6]
After : [0,0,1,1,2,2,2,2,3.5,4,5,6,7,8,9]
Writes : 10
Before : [4,65,2,-31,0,99,2,83,782,1]
After : [-31,0,1,2,2,4,65,83,99,782]
Writes : 9
Before : [7,5,2,6,1,4,2,6,3]
After : [1,2,2,3,4,5,6,6,7]
Writes : 7
</pre>
=={{header|Julia}}==
| |||