Sorting algorithms/Cycle sort

Sorting algorithms/Cycle sort is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

For more information on cycle sorting, see the Wikipedia entry.

Go

This implementation was translated from the example code on Wikipedia.

<lang go>package main

import ( "fmt" "math/rand" "time" )

func cyclesort(ints []int) int { writes := 0

for cyclestart := 0; cyclestart < len(ints)-1; cyclestart++ { item := ints[cyclestart]

pos := cyclestart

for i := cyclestart + 1; i < len(ints); i++ { if ints[i] < item { pos++ } }

if pos == cyclestart { continue }

for item == ints[pos] { pos++ }

ints[pos], item = item, ints[pos]

writes++

for pos != cyclestart { pos = cyclestart for i := cyclestart + 1; i < len(ints); i++ { if ints[i] < item { pos++ } }

for item == ints[pos] { pos++ }

ints[pos], item = item, ints[pos] writes++ } }

return writes }

func main() { rand.Seed(time.Now().Unix())

ints := rand.Perm(10)

fmt.Println(ints) fmt.Printf("writes %d\n", cyclesort(ints)) fmt.Println(ints) }</lang>

Output:

[1 9 3 5 8 4 7 0 6 2]
writes 10
[0 1 2 3 4 5 6 7 8 9]

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

Perl 6

<lang perl6>sub cycle_sort ( @nums is rw ) {

   my $writes = 0;

   # Loop through the array to find cycles to rotate.
   for @nums.kv -> $cycle_start, $item is copy {

       # Find where to put the item.
       my $pos = $cycle_start
               + @nums[ $cycle_start ^.. * ].grep: * < $item;

       # If the item is already there, this is not a cycle.
       next if $pos == $cycle_start;

       # Otherwise, put the item there or right after any duplicates.
       $pos++ while $item == @nums[$pos];
       ( @nums[$pos], $item ) .= reverse;
       $writes++;

       # Rotate the rest of the cycle.
       while $pos != $cycle_start {

           # Find where to put the item.
           $pos = $cycle_start
                + @nums[ $cycle_start ^.. * ].grep: * < $item;

           # Put the item there or right after any duplicates.
           $pos++ while $item == @nums[$pos];
           ( @nums[$pos], $item ) .= reverse;
           $writes++;
       }
   }

   return $writes;

}

my @a = <0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6>;

say @a; say 'writes ', cycle_sort(@a); say @a; </lang>

Output:

0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6
writes 10
0 0 1 1 2 2 2 2 3.5 4 5 6 7 8 9