Sorting algorithms/Cycle sort: Difference between revisions

 

<br>

* [http://www.youtube.com/watch?v=ZSJGf5Ngw18 Youtube] Visualization and audibilization of Cycle Sort algorithm.

<br><br>

 

=={{header|360 Assembly}}==

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

-31 0 1 2 2 4 45 58 65 69 74 82 82 83 88 89 99 104 112 782

</pre>

 

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

writes : 10

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

</pre>

 

This implementation was translated from the example code on Wikipedia.

 

 

import (

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

fmt.Println(ints)

 

{{out}}

 

Note: output may be different due to the random numbers used.

 

=={{header|J}}==

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

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

Sorted list [George Washington: Virginia, James Madison: Virginia, James Monroe: Virginia, John Adams: Massachusetts, Thomas Jefferson: Virginia]

Total number of writes: 4</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;

 

my ($array) = @_;

my $writes = 0;

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

After sorting: a a b b c c d d e e f f g g h h i i j j k k l l m m n n o o p p q q r r s s t t u u v v w w x x y y z z</pre>

 

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

'#(1 1 1 1 1 1)

0</pre>

 

=={{header|REXX}}==

===version 1===

* 12.06.2014 Walter Pachl translated from Wikipedia's code

* 20.06.2014 WP corrected (courtesy Alan Sampson)

**********************************************************************/

list='1 9 3 5 8 4 7 0 6 2'

cycleSort: procedure expose array. n

writes = 0

do cycleStart=0 to n-2

item = array.cycleStart

 

pos = cycleStart

Do i=cycleStart+1 to n-1

if array.i < item Then

End

 

if pos == cycleStart Then

Iterate

 

Do while item == array.pos

End

Parse Value array.pos item With item array.pos

 

Do while pos <> cycleStart

 

pos = cycleStart

Do i=cycleStart + 1 to n-1

if array.i < item Then

End

 

Do while item == array.pos

End

Parse Value array.pos item With item array.pos

End

End

{{out}}

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

 

===version 2===

 

As a default, the program uses (for the input list) some digits of pi, which for practical purposes, appear random.

say 'unsorted list: ' z /*show the original unsorted numbers. */

exit /*stick a fork in it, we're all done. */

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

end /*c*/

<pre>

unsorted list: -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

sorted list: -3.14 0 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 7 7 8 8 8 8 8 9 9 9 9

</pre>

<pre>

unsorted list: FM Stereo has been around since 1961.

sorted list: 1961. FM Stereo around been has since

</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)

 

func f(i, Ref item, bool=false) {

return(false) if (bool && pos==i)

while (*item == array[pos]) { ++pos }

array.each_kv { |i, item|

f(i, \item, true) || next

f(i, \item)

}

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>

Writes required: 10

</pre>