Sorting algorithms/Cycle sort

Sorting algorithms/Cycle sort
You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

Heap sort | Merge sort | Patience sort | Quick sort

O(n log²n) sorts
Shell Sort

O(n²) sorts
Bubble sort | Cocktail sort | Cocktail sort with shifting bounds | Comb sort | Cycle sort | Gnome sort | Insertion sort | Selection sort | Strand sort

other sorts
Bead sort | Bogo sort | Common sorted list | Composite structures sort | Custom comparator sort | Counting sort | Disjoint sublist sort | External sort | Jort sort | Lexicographical sort | Natural sorting | Order by pair comparisons | Order disjoint list items | Order two numerical lists | Object identifier (OID) sort | Pancake sort | Quickselect | Permutation sort | Radix sort | Ranking methods | Remove duplicate elements | Sleep sort | Stooge sort | [Sort letters of a string] | Three variable sort | Topological sort | Tree sort

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.