Sorting algorithms/Cycle sort: Difference between revisions
Content added Content deleted
Drkameleon (talk | contribs) (Added Arturo implementation) |
|||
Line 979: | Line 979: | ||
[0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 5, 5, 6, 8, 9] |
[0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 5, 5, 6, 8, 9] |
||
writes: 14</pre> |
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}}== |
=={{header|Julia}}== |