Sorting algorithms/Cycle sort: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 24: | Line 24: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">F cycleSort(&vector) |
||
V writes = 0 |
V writes = 0 |
||
Line 62: | Line 62: | ||
E |
E |
||
print("#.\nIs correctly sorted using cycleSort to".format(x)) |
print("#.\nIs correctly sorted using cycleSort to".format(x)) |
||
print("#.\nUsing #. writes.".format(xcopy, writes))</ |
print("#.\nUsing #. writes.".format(xcopy, writes))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 75: | Line 75: | ||
{{trans|NetRexx}} |
{{trans|NetRexx}} |
||
The program uses ASM structured macros and two ASSIST macros to keep the code as short as possible. |
The program uses ASM structured macros and two ASSIST macros to keep the code as short as possible. |
||
< |
<syntaxhighlight lang="360asm">* Cycle sort 26/06/2016 |
||
CYCLESRT CSECT |
CYCLESRT CSECT |
||
USING CYCLESRT,R13 base register |
USING CYCLESRT,R13 base register |
||
Line 185: | Line 185: | ||
RT EQU 9 temp |
RT EQU 9 temp |
||
RM EQU 10 item |
RM EQU 10 item |
||
END CYCLESRT</ |
END CYCLESRT</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 192: | Line 192: | ||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
< |
<syntaxhighlight lang="action!">PROC PrintArray(INT ARRAY a INT size) |
||
INT i |
INT i |
||
Line 263: | Line 263: | ||
Test(c,8) |
Test(c,8) |
||
Test(d,12) |
Test(d,12) |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Cycle_sort.png Screenshot from Atari 8-bit computer] |
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Cycle_sort.png Screenshot from Atari 8-bit computer] |
||
Line 290: | Line 290: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">cycleSort: function [items][ |
||
a: new items |
a: new items |
||
position: 0 |
position: 0 |
||
Line 321: | Line 321: | ||
] |
] |
||
print cycleSort [3 1 2 8 5 7 9 4 6]</ |
print cycleSort [3 1 2 8 5 7 9 4 6]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 328: | Line 328: | ||
=={{header|BCPL}}== |
=={{header|BCPL}}== |
||
< |
<syntaxhighlight lang="bcpl">get "libhdr" |
||
// Sort an array in place and return the number of writes |
// Sort an array in place and return the number of writes |
||
Line 386: | Line 386: | ||
writes("After: ") ; writevec(v, l) |
writes("After: ") ; writevec(v, l) |
||
writef("Writes: %N*N", w) |
writef("Writes: %N*N", w) |
||
$)</ |
$)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Before: 0 1 2 2 2 2 1 9 3 5 5 8 4 7 0 6 |
<pre>Before: 0 1 2 2 2 2 1 9 3 5 5 8 4 7 0 6 |
||
Line 394: | Line 394: | ||
=={{header|C}}== |
=={{header|C}}== |
||
{{trans|NetRexx}} |
{{trans|NetRexx}} |
||
<syntaxhighlight lang="c"> |
|||
<lang C> |
|||
#include <stdio.h> |
#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 492: | Line 492: | ||
return; |
return; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 502: | Line 502: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
Based on example code on Wikipedia |
Based on example code on Wikipedia |
||
<syntaxhighlight lang="cpp"> |
|||
<lang Cpp> |
|||
#include <time.h> |
#include <time.h> |
||
#include <iostream> |
#include <iostream> |
||
Line 568: | Line 568: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 579: | Line 579: | ||
This version doesn't use Phobos algorithms beside 'swap'. Algorithms can be used to find where to put the item1 and elsewhere. |
This version doesn't use Phobos algorithms beside 'swap'. Algorithms can be used to find where to put the item1 and elsewhere. |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.algorithm; |
||
/// Sort an array in place and return the number of writes. |
/// Sort an array in place and return the number of writes. |
||
Line 633: | Line 633: | ||
writefln("%s\nusing %d writes.", xs, nWrites); |
writefln("%s\nusing %d writes.", xs, nWrites); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6] |
<pre>[0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6] |
||
Line 642: | Line 642: | ||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang="elixir">defmodule Sort do |
||
def cycleSort(list) do |
def cycleSort(list) do |
||
tuple = List.to_tuple(list) |
tuple = List.to_tuple(list) |
||
Line 684: | Line 684: | ||
{b, writes} = Sort.cycleSort(a) |
{b, writes} = Sort.cycleSort(a) |
||
IO.puts "writes : #{writes}" |
IO.puts "writes : #{writes}" |
||
IO.inspect b</ |
IO.inspect b</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 695: | Line 695: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
Uses algorithm in Wikipedia article: |
Uses algorithm in Wikipedia article: |
||
< |
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64 |
||
' sort an array in place and return the number of writes |
' sort an array in place and return the number of writes |
||
Line 763: | Line 763: | ||
Print |
Print |
||
Print "Press any key to quit" |
Print "Press any key to quit" |
||
Sleep</ |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 779: | Line 779: | ||
This implementation was translated from the example code on Wikipedia. |
This implementation was translated from the example code on Wikipedia. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 841: | Line 841: | ||
fmt.Printf("writes %d\n", cyclesort(ints)) |
fmt.Printf("writes %d\n", cyclesort(ints)) |
||
fmt.Println(ints) |
fmt.Println(ints) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 854: | Line 854: | ||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="groovy">class CycleSort { |
||
static void main(String[] args) { |
static void main(String[] args) { |
||
int[] arr = [5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1] |
int[] arr = [5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1] |
||
Line 918: | Line 918: | ||
return writes |
return writes |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1] |
<pre>[5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1] |
||
Line 929: | Line 929: | ||
It would be trivial do the writes one at a time, and to avoid updating values which are not changed: |
It would be trivial do the writes one at a time, and to avoid updating values which are not changed: |
||
< |
<syntaxhighlight lang="j">noncyc=:3 :0 |
||
writes=. 0 |
writes=. 0 |
||
for_item. /:~y do. |
for_item. /:~y do. |
||
Line 939: | Line 939: | ||
smoutput (":writes),' writes' |
smoutput (":writes),' writes' |
||
y |
y |
||
)</ |
)</syntaxhighlight> |
||
{{out|Example use}} |
{{out|Example use}} |
||
< |
<syntaxhighlight lang="j"> noncyc 9 8 15 17 4 0 1 2 17 9 3 12 11 12 19 15 3 9 16 9 |
||
17 writes |
17 writes |
||
0 1 2 3 3 4 8 9 9 9 9 11 12 12 15 15 16 17 17 19</ |
0 1 2 3 3 4 8 9 9 9 9 11 12 12 15 15 16 17 17 19</syntaxhighlight> |
||
Meanwhile, if we just wanted the "value at a time swapping" mechanism, |
Meanwhile, if we just wanted the "value at a time swapping" mechanism, |
||
an idiomatic approach might look something like this: |
an idiomatic approach might look something like this: |
||
< |
<syntaxhighlight lang="j">cyc0=:3 :0 |
||
c=. (#~ 1 < #@>)C./:/: y |
c=. (#~ 1 < #@>)C./:/: y |
||
writes=. 0 |
writes=. 0 |
||
Line 964: | Line 964: | ||
smoutput (":writes),' writes' |
smoutput (":writes),' writes' |
||
y |
y |
||
)</ |
)</syntaxhighlight> |
||
{{out|Example use}} |
{{out|Example use}} |
||
< |
<syntaxhighlight lang="j"> cyc0 9 8 15 17 4 0 1 2 17 9 3 12 11 12 19 15 3 9 16 9 |
||
18 writes |
18 writes |
||
0 1 2 3 3 4 8 9 9 9 9 11 12 12 15 15 16 17 17 19</ |
0 1 2 3 3 4 8 9 9 9 9 11 12 12 15 15 16 17 17 19</syntaxhighlight> |
||
This gives us an extra write, because we're using a generic cycle abstraction. |
This gives us an extra write, because we're using a generic cycle abstraction. |
||
Line 976: | Line 976: | ||
We might model the wikipedia algorithm like this: |
We might model the wikipedia algorithm like this: |
||
< |
<syntaxhighlight lang="j">cyc1=:3 :0 |
||
writes=. 0 |
writes=. 0 |
||
for_index. i.(#y)-1 do. |
for_index. i.(#y)-1 do. |
||
Line 1,000: | Line 1,000: | ||
smoutput (":writes),' writes' |
smoutput (":writes),' writes' |
||
y |
y |
||
)</ |
)</syntaxhighlight> |
||
{{out|Example use}} |
{{out|Example use}} |
||
< |
<syntaxhighlight lang="j"> cyc1 9 8 15 17 4 0 1 2 17 9 3 12 11 12 19 15 3 9 16 9 |
||
17 writes |
17 writes |
||
0 1 2 3 3 4 8 9 9 9 9 11 12 12 15 15 16 17 17 19</ |
0 1 2 3 3 4 8 9 9 9 9 11 12 12 15 15 16 17 17 19</syntaxhighlight> |
||
Note that we've saved a write in this case, by following the wikipedia algorithm. |
Note that we've saved a write in this case, by following the wikipedia algorithm. |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java">import java.util.Arrays; |
||
public class CycleSort { |
public class CycleSort { |
||
Line 1,070: | Line 1,070: | ||
return writes; |
return writes; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,084: | Line 1,084: | ||
The following implementation is based on the [[#Wren|Wren]] entry except for the |
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`. |
use of `swap`, which exposes a bug in the Wren version (as of 2021.09.12) regarding `writes`. |
||
<syntaxhighlight lang="jq"> |
|||
<lang jq> |
|||
# Output: {a: sortedInput, write: numberOfSwaps} |
# Output: {a: sortedInput, write: numberOfSwaps} |
||
def cycleSort: |
def cycleSort: |
||
Line 1,106: | Line 1,106: | ||
else . |
else . |
||
end ) |
end ) |
||
| {a, writes} ;</ |
| {a, writes} ;</syntaxhighlight> |
||
'''The Task''' |
'''The Task''' |
||
< |
<syntaxhighlight 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], |
[4, 65, 2, -31, 0, 99, 2, 83, 782, 1], |
||
[7, 5, 2, 6, 1, 4, 2, 6, 3] |
[7, 5, 2, 6, 1, 4, 2, 6, 3] |
||
Line 1,115: | Line 1,115: | ||
| "After : \(.a)", |
| "After : \(.a)", |
||
"Writes : \(.writes)", |
"Writes : \(.writes)", |
||
"")</ |
"")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,135: | Line 1,135: | ||
{{works with|Julia|0.6}} |
{{works with|Julia|0.6}} |
||
< |
<syntaxhighlight lang="julia">function cyclesort!(v::Vector) |
||
writes = 0 |
writes = 0 |
||
for (cyclestart, item) in enumerate(v) |
for (cyclestart, item) in enumerate(v) |
||
Line 1,167: | Line 1,167: | ||
v = rand(-10:10, 10) |
v = rand(-10:10, 10) |
||
println("# unordered: $v\n -> ordered: ", cyclesort!(v))</ |
println("# unordered: $v\n -> ordered: ", cyclesort!(v))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,175: | Line 1,175: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
Translation of the algorithm in the Wikipedia article: |
Translation of the algorithm in the Wikipedia article: |
||
< |
<syntaxhighlight lang="scala">// version 1.1.0 |
||
/** Sort an array in place and return the number of writes */ |
/** Sort an array in place and return the number of writes */ |
||
Line 1,233: | Line 1,233: | ||
val array4 = "sphinx of black quartz judge my vow".replace(" ", "").toCharArray().distinct().toTypedArray() |
val array4 = "sphinx of black quartz judge my vow".replace(" ", "").toCharArray().distinct().toTypedArray() |
||
printResults(array4) |
printResults(array4) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,256: | Line 1,256: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="lua">function printa(a) |
||
io.write("[") |
io.write("[") |
||
for i,v in ipairs(a) do |
for i,v in ipairs(a) do |
||
Line 1,329: | Line 1,329: | ||
printa(arr) |
printa(arr) |
||
print() |
print() |
||
print("writes: " .. writes)</ |
print("writes: " .. writes)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1] |
<pre>[5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1] |
||
Line 1,337: | Line 1,337: | ||
=={{header|NetRexx}}== |
=={{header|NetRexx}}== |
||
Direct translation of [[wp:Cycle sort|the Wikipedia entry]] example |
Direct translation of [[wp:Cycle sort|the Wikipedia entry]] example |
||
< |
<syntaxhighlight lang="netrexx">/* Rexx */ |
||
options replace format comments java crossref symbols nobinary |
options replace format comments java crossref symbols nobinary |
||
Line 1,415: | Line 1,415: | ||
end i_ |
end i_ |
||
return |
return |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,439: | Line 1,439: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">proc cycleSort[T](a: var openArray[T]): int = |
||
var position, writes: int = 0 |
var position, writes: int = 0 |
||
var item: T |
var item: T |
||
Line 1,495: | Line 1,495: | ||
writes = array5.cycleSort() |
writes = array5.cycleSort() |
||
echo "Sorted: ", $array5 |
echo "Sorted: ", $array5 |
||
echo "Total number of writes: ", writes</ |
echo "Total number of writes: ", writes</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,520: | Line 1,520: | ||
=={{header|Objeck}}== |
=={{header|Objeck}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="objeck">class Test { |
||
function : Main(args : String[]) ~ Nil { |
function : Main(args : String[]) ~ Nil { |
||
arr := [5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1]; |
arr := [5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1]; |
||
Line 1,574: | Line 1,574: | ||
return writes; |
return writes; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<pre> |
<pre> |
||
Line 1,583: | Line 1,583: | ||
=={{header|ooRexx}}== |
=={{header|ooRexx}}== |
||
< |
<syntaxhighlight lang="oorexx">/*REXX program demonstrates a cycle sort on a list of numbers********** |
||
* 13.06.2014 Walter Pachl |
* 13.06.2014 Walter Pachl |
||
* Modified from Rexx Version 2 |
* Modified from Rexx Version 2 |
||
Line 1,647: | Line 1,647: | ||
Say format(i,2) a.i |
Say format(i,2) a.i |
||
End |
End |
||
Return</ |
Return</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,669: | Line 1,669: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
This is based on the Wikipedia pseudocode. |
This is based on the Wikipedia pseudocode. |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
Line 1,716: | Line 1,716: | ||
print "There were ", cycleSort( \@test ), " writes\n"; |
print "There were ", cycleSort( \@test ), " writes\n"; |
||
print "After sorting: @test\n"; |
print "After sorting: @test\n"; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>Before sorting: a t d b f g y l t p w c r r x i y j k i z q e v a f o q j u x k m h s u v z g m b o l e n h p n c s w d |
<pre>Before sorting: a t d b f g y l t p w c r r x i y j k i z q e v a f o q j u x k m h s u v z g m b o l e n h p n c s w d |
||
Line 1,725: | Line 1,725: | ||
{{trans|NetRexx}} |
{{trans|NetRexx}} |
||
plus some factoring out of common code |
plus some factoring out of common code |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
Line 1,787: | Line 1,787: | ||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Total number of writes: %d (out of %d)\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">writes</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">array</span><span style="color: #0000FF;">)})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Total number of writes: %d (out of %d)\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">writes</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">array</span><span style="color: #0000FF;">)})</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,813: | Line 1,813: | ||
The Wikipedia algorithm pseudocode is very nearly Python. The main changes needed were to change the name array to vector to stop it obscuring a built-in name, and iterating over an enumerated collection rather than using explicit indices. |
The Wikipedia algorithm pseudocode is very nearly Python. The main changes needed were to change the name array to vector to stop it obscuring a built-in name, and iterating over an enumerated collection rather than using explicit indices. |
||
< |
<syntaxhighlight lang="python">def cycleSort(vector): |
||
"Sort a vector in place and return the number of writes." |
"Sort a vector in place and return the number of writes." |
||
writes = 0 |
writes = 0 |
||
Line 1,862: | Line 1,862: | ||
else: |
else: |
||
print('%r\nIs correctly sorted using cycleSort to' |
print('%r\nIs correctly sorted using cycleSort to' |
||
'\n%r\nUsing %i writes.' % (x, xcopy, writes))</ |
'\n%r\nUsing %i writes.' % (x, xcopy, writes))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,871: | Line 1,871: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket/base |
||
(require racket/match) |
(require racket/match) |
||
Line 1,912: | Line 1,912: | ||
(define B #(1 1 1 1 1 1)) |
(define B #(1 1 1 1 1 1)) |
||
B |
B |
||
(cycle-sort! B < =))</ |
(cycle-sort! B < =))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,923: | Line 1,923: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
(formerly Perl 6) |
(formerly Perl 6) |
||
<lang |
<syntaxhighlight lang="raku" line>sub cycle_sort ( @nums ) { |
||
my $writes = 0; |
my $writes = 0; |
||
Line 1,963: | Line 1,963: | ||
say 'writes ', cycle_sort(@a); |
say 'writes ', cycle_sort(@a); |
||
say @a; |
say @a; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6 |
<pre>0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6 |
||
Line 1,972: | Line 1,972: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===version 1=== |
===version 1=== |
||
< |
<syntaxhighlight lang="rexx">/* REXX *************************************************************** |
||
* 12.06.2014 Walter Pachl translated from Wikipedia's code |
* 12.06.2014 Walter Pachl translated from Wikipedia's code |
||
* 20.06.2014 WP corrected (courtesy Alan Sampson) |
* 20.06.2014 WP corrected (courtesy Alan Sampson) |
||
Line 2,034: | Line 2,034: | ||
End |
End |
||
End |
End |
||
return writes</ |
return writes</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 9 3 5 8 4 7 0 6 2 |
<pre>1 9 3 5 8 4 7 0 6 2 |
||
Line 2,044: | Line 2,044: | ||
As a default, the program uses (for the input list) some digits of pi, which for practical purposes, appear random. |
As a default, the program uses (for the input list) some digits of pi, which for practical purposes, appear random. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program performs a cycle sort on a list of items (could be numbers or text).*/ |
||
parse arg z /*obtain optional arguments from the CL*/ |
parse arg z /*obtain optional arguments from the CL*/ |
||
if z='' then z= -3.14 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 |
if z='' then z= -3.14 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 |
||
Line 2,069: | Line 2,069: | ||
y=@.1; do m=2 for #-1; y=y @.m; end; return mv /*put the array back into the Y list.*/ |
y=@.1; do m=2 for #-1; y=y @.m; end; return mv /*put the array back into the Y list.*/ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
.putX: mv= mv+1; do p=p while x==@.p; end; parse value @.p x with x @.p; return</ |
.putX: mv= mv+1; do p=p while x==@.p; end; parse value @.p x with x @.p; return</syntaxhighlight> |
||
{{out|output|text= when using the default input:}} |
{{out|output|text= when using the default input:}} |
||
<pre> |
<pre> |
||
Line 2,088: | Line 2,088: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
# Project : Sorting algorithms/Cycle sort |
# Project : Sorting algorithms/Cycle sort |
||
Line 2,150: | Line 2,150: | ||
next |
next |
||
see nl |
see nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 2,164: | Line 2,164: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
Direct translation of the pseudocode on the Wikipedia. |
Direct translation of the pseudocode on the Wikipedia. |
||
< |
<syntaxhighlight lang="ruby">def cycleSort!(array) |
||
writes = 0 |
writes = 0 |
||
Line 2,205: | Line 2,205: | ||
p a = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6] |
p a = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6] |
||
puts "writes : #{cycleSort!(a)}" |
puts "writes : #{cycleSort!(a)}" |
||
p a</ |
p a</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,216: | Line 2,216: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
Translation of Java version |
Translation of Java version |
||
< |
<syntaxhighlight lang="scala"> |
||
def cycleSort(a: Array[Int]): (Array[Int], Int) = { |
def cycleSort(a: Array[Int]): (Array[Int], Int) = { |
||
var writes = 0 |
var writes = 0 |
||
Line 2,259: | Line 2,259: | ||
(a, writes) |
(a, writes) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func cycle_sort (array) { |
||
var (writes=0, pos=0) |
var (writes=0, pos=0) |
||
Line 2,288: | Line 2,288: | ||
say a.join(' ') |
say a.join(' ') |
||
say ('writes ', cycle_sort(a)) |
say ('writes ', cycle_sort(a)) |
||
say a.join(' ')</ |
say a.join(' ')</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,298: | Line 2,298: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
Direct translation of the pseudocode on the Wikipedia page |
Direct translation of the pseudocode on the Wikipedia page |
||
< |
<syntaxhighlight lang="tcl">proc cycleSort {listVar} { |
||
upvar 1 $listVar array |
upvar 1 $listVar array |
||
set writes 0 |
set writes 0 |
||
Line 2,345: | Line 2,345: | ||
return $writes |
return $writes |
||
}</ |
}</syntaxhighlight> |
||
'''Demonstrating:''' |
'''Demonstrating:''' |
||
< |
<syntaxhighlight lang="tcl">set example {0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6} |
||
puts "Data was: $example" |
puts "Data was: $example" |
||
set writes [cycleSort example] |
set writes [cycleSort example] |
||
Line 2,356: | Line 2,356: | ||
puts "\twhich is the wrong order!" |
puts "\twhich is the wrong order!" |
||
} |
} |
||
puts "Writes required: $writes"</ |
puts "Writes required: $writes"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,367: | Line 2,367: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
Translation of the Python code in the Wikipedia article. |
Translation of the Python code in the Wikipedia article. |
||
< |
<syntaxhighlight lang="ecmascript">var cycleSort = Fn.new { |a| |
||
var writes = 0 |
var writes = 0 |
||
var len = a.count |
var len = a.count |
||
Line 2,404: | Line 2,404: | ||
System.print("Writes : %(w)") |
System.print("Writes : %(w)") |
||
System.print() |
System.print() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,419: | Line 2,419: | ||
=={{header|Yabasic}}== |
=={{header|Yabasic}}== |
||
{{trans|FreeBASIC}} |
{{trans|FreeBASIC}} |
||
< |
<syntaxhighlight lang="yabasic">// Rosetta Code problem: http://rosettacode.org/wiki/Cycle_sort |
||
// by Galileo, 04/2022 |
// by Galileo, 04/2022 |
||
Line 2,483: | Line 2,483: | ||
printArray(ints()) |
printArray(ints()) |
||
print "writes ", cyclesort(ints()) |
print "writes ", cyclesort(ints()) |
||
printArray(ints())</ |
printArray(ints())</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>9 9 9 6 8 1 9 7 3 4 |
<pre>9 9 9 6 8 1 9 7 3 4 |