Sorting algorithms/Cycle sort: Difference between revisions

 

 

;See also:

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

 

=={{header|C}}==

{{trans|NetRexx}}

#include <stdio.h>

#include <stdlib.h>

return;

}

{{out}}

<pre>

0 0 1 1 2 2 2 2 3 4 5 5 6 7 8 9

writes: 10

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

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

using 10 writes.</pre>

 

=={{header|Go}}==

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

 

 

writes=. 0

for_item. /:~y do.

smoutput (":writes),' writes'

y

 

17 writes

 

 

c=. (#~ 1 < #@>)C./:/: y

writes=. 0

smoutput (":writes),' writes'

y

 

18 writes

 

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

 

 

writes=. 0

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

smoutput (":writes),' writes'

y

 

17 writes

 

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

 

=={{header|Java}}==

 

public class CycleSort {

return writes;

}

 

 

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

[0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 5, 5, 6, 8, 9]

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

There were 50 writes

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

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

Using 10 writes.</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.

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

Translation of Java version

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

var writes = 0

(a, writes)

}

 

=={{header|Tcl}}==

Direct translation of the pseudocode on the Wikipedia page

upvar 1 $listVar array

set writes 0

return $writes

puts "Data was: $example"

set writes [cycleSort example]

puts "\twhich is the wrong order!"

}

{{out}}

<pre>

Writes required: 10

</pre>