Sorting algorithms/Cycle sort: Difference between revisions

{{trans|Python}}

 

V writes = 0

 

E

print("#.\nIs correctly sorted using cycleSort to".format(x))

 

{{out}}

{{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

RT EQU 9 temp

RM EQU 10 item

{{out}}

<pre>

 

=={{header|Action!}}==

INT i

 

Test(c,8)

Test(d,12)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Cycle_sort.png Screenshot from Atari 8-bit computer]

=={{header|Arturo}}==

 

a: new items

position: 0

]

 

 

{{out}}

 

=={{header|BCPL}}==

 

// Sort an array in place and return the number of writes

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

=={{header|C}}==

{{trans|NetRexx}}

#include <stdio.h>

#include <stdlib.h>

return;

}

{{out}}

<pre>

=={{header|C++}}==

Based on example code on Wikipedia

#include <time.h>

#include <iostream>

return 0;

}

{{out}}

<pre>

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.

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]

=={{header|Elixir}}==

{{trans|Ruby}}

def cycleSort(list) do

tuple = List.to_tuple(list)

{b, writes} = Sort.cycleSort(a)

IO.puts "writes : #{writes}"

 

{{out}}

=={{header|FreeBASIC}}==

Uses algorithm in Wikipedia article:

 

' sort an array in place and return the number of writes

Print

Print "Press any key to quit"

 

{{out}}

This implementation was translated from the example code on Wikipedia.

 

 

import (

fmt.Printf("writes %d\n", cyclesort(ints))

fmt.Println(ints)

 

{{out}}

=={{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]

return writes

}

{{out}}

<pre>[5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1]

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.

smoutput (":writes),' writes'

y

 

{{out|Example use}}

17 writes

 

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

smoutput (":writes),' writes'

y

 

{{out|Example use}}

18 writes

 

This gives us an extra write, because we're using a generic cycle abstraction.

We might model the wikipedia algorithm like this:

 

writes=. 0

for_index. i.(#y)-1 do.

smoutput (":writes),' writes'

y

 

{{out|Example use}}

17 writes

 

Note that we've saved a write in this case, by following the wikipedia algorithm.

 

=={{header|Java}}==

 

public class CycleSort {

return writes;

}

 

{{out}}

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`.

# Output: {a: sortedInput, write: numberOfSwaps}

def cycleSort:

else .

end )

'''The Task'''

[4, 65, 2, -31, 0, 99, 2, 83, 782, 1],

[7, 5, 2, 6, 1, 4, 2, 6, 3]

| "After : \(.a)",

"Writes : \(.writes)",

{{out}}

<pre>

{{works with|Julia|0.6}}

 

writes = 0

for (cyclestart, item) in enumerate(v)

 

v = rand(-10:10, 10)

 

{{out}}

=={{header|Kotlin}}==

Translation of the algorithm in the Wikipedia article:

 

/** Sort an array in place and return the number of writes */

val array4 = "sphinx of black quartz judge my vow".replace(" ", "").toCharArray().distinct().toTypedArray()

printResults(array4)

 

{{out}}

=={{header|Lua}}==

{{trans|Java}}

io.write("[")

for i,v in ipairs(a) do

printa(arr)

print()

{{out}}

<pre>[5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1]

=={{header|NetRexx}}==

Direct translation of [[wp:Cycle sort|the Wikipedia entry]] example

options replace format comments java crossref symbols nobinary

 

end i_

return

{{out}}

<pre>

 

=={{header|Nim}}==

var position, writes: int = 0

var item: T

writes = array5.cycleSort()

echo "Sorted: ", $array5

 

{{out}}

=={{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];

return writes;

}

 

<pre>

 

=={{header|ooRexx}}==

* 13.06.2014 Walter Pachl

* Modified from Rexx Version 2

Say format(i,2) a.i

End

{{out}}

<pre>

=={{header|Perl}}==

This is based on the Wikipedia pseudocode.

use warnings;

 

print "There were ", cycleSort( \@test ), " writes\n";

print "After sorting: @test\n";

{{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

{{trans|NetRexx}}

plus some factoring out of common code

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</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>

{{out}}

<pre>

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

else:

print('%r\nIs correctly sorted using cycleSort to'

 

{{out}}

 

=={{header|Racket}}==

(require racket/match)

 

(define B #(1 1 1 1 1 1))

B

 

{{out}}

=={{header|Raku}}==

(formerly Perl 6)

my $writes = 0;

 

say 'writes ', cycle_sort(@a);

say @a;

{{out}}

<pre>0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6

=={{header|REXX}}==

===version 1===

* 12.06.2014 Walter Pachl translated from Wikipedia's code

* 20.06.2014 WP corrected (courtesy Alan Sampson)

End

End

{{out}}

<pre>1 9 3 5 8 4 7 0 6 2

 

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

y=@.1; do m=2 for #-1; y=y @.m; end; return mv /*put the array back into the Y list.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

=={{header|Ring}}==

# Project : Sorting algorithms/Cycle sort

 

next

see nl

Output:

<pre>

=={{header|Ruby}}==

Direct translation of the pseudocode on the Wikipedia.

writes = 0

p a = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]

puts "writes : #{cycleSort!(a)}"

 

{{out}}

=={{header|Scala}}==

Translation of Java version

def cycleSort(a: Array[Int]): (Array[Int], Int) = {

var writes = 0

(a, writes)

}

 

=={{header|Sidef}}==

var (writes=0, pos=0)

 

say a.join(' ')

say ('writes ', cycle_sort(a))

{{out}}

<pre>

=={{header|Tcl}}==

Direct translation of the pseudocode on the Wikipedia page

upvar 1 $listVar array

set writes 0

return $writes

'''Demonstrating:'''

puts "Data was: $example"

set writes [cycleSort example]

puts "\twhich is the wrong order!"

}

{{out}}

<pre>

=={{header|Wren}}==

Translation of the Python code in the Wikipedia article.

var writes = 0

var len = a.count

System.print("Writes : %(w)")

System.print()

 

{{out}}

=={{header|Yabasic}}==

{{trans|FreeBASIC}}

// by Galileo, 04/2022

 

printArray(ints())

print "writes ", cyclesort(ints())

{{out}}

<pre>9 9 9 6 8 1 9 7 3 4