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