Sorting algorithms/Cycle sort: Difference between revisions

=={{header|Perl}}==

This is based on the Wikipedia pseudocode.

<lang perl>use strict;

use warnings;

sub cycleSort(@) {

my ($array) = @_;

my $writes = 0;

my @alreadysorted;

# For each index except the last:

for my $start ( 0 .. $#$array - 1 ) {

next if $alreadysorted[$start];

my $item = $array->[$start];

# If there are N items less than $item, then we

# must move $item N items rightward.

my $pos = $start + grep $array->[$_] lt $item, $start + 1 .. $#$array;

# If the item is where it should be, continue.

next if $pos == $start;

# If $item is one of several repetitions, move it to the right

# of the last repeat.

++$pos while $item eq $array->[ $pos ];

# Store $item at $pos, where it belongs, and fetch the

# value that had been at $pos, and put it in $item.

($array->[ $pos ], $item) = ($item, $array->[ $pos ]);

++$writes;

# Whatever $item is now, it certainly doesn't belong at $pos;

do {

# Find the correct $pos,

$pos = $start + grep $array->[$_] lt $item, $start+1 .. $#$array;

++$pos while $item eq $array->[ $pos ];

# Swap the value there with $item,

($array->[ $pos ] , $item ) = ($item, $array->[ $pos ]);

# And mark $pos as having the correct value in it..

$alreadysorted[ $pos ] = 1;

++$writes;

# The loop ends after we have just written an item to $start

} while $pos != $start;

}

$writes;

}

use List::Util 'shuffle';

my @test = shuffle( ('a'..'z') x 2 );

print "Before sorting: @test\n";

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

print "After sorting: @test\n";

</lang>

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