Sorting algorithms/Cycle sort: Difference between revisions
(Created page with "{{task|Sorting Algorithms}}{{Sorting Algorithm}} For more information on cycle sorting, see the Wikipedia entry. =={{header|Go}}== This implementation was ...") |
m (Start as a draft, don't add the sorting algorithms box yet) |
||
Line 1: | Line 1: | ||
{{task|Sorting Algorithms}}{{Sorting Algorithm}} |
{{draft task|Sorting Algorithms}}<!--Add this back when it gets promoted, also add a link to this page to the n^2 sorts in the template{{Sorting Algorithm}}--> |
||
For more information on cycle sorting, see [[wp:Cycle sort|the Wikipedia entry]]. |
For more information on cycle sorting, see [[wp:Cycle sort|the Wikipedia entry]]. |
||
Line 70: | Line 70: | ||
}</lang> |
}</lang> |
||
{{out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
[1 9 3 5 8 4 7 0 6 2] |
[1 9 3 5 8 4 7 0 6 2] |
Revision as of 03:05, 12 June 2014
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.