Sorting algorithms/Cycle sort: Difference between revisions

Content added Content deleted
m (→‎version 4: changed alignment of a couple of comments.)
m (→‎version 1: fixed for Cöassic Rexx)
Line 1,302: Line 1,302:
* 12.06.2014 Walter Pachl translated from Wikipedia's code
* 12.06.2014 Walter Pachl translated from Wikipedia's code
* 20.06.2014 WP corrected (courtesy Alan Sampson)
* 20.06.2014 WP corrected (courtesy Alan Sampson)
* 30.05.2017 WP fixed for Classic Rexx (courtesy GS)
**********************************************************************/
**********************************************************************/
list='1 9 3 5 8 4 7 0 6 2'
list='1 9 3 5 8 4 7 0 6 2'
Line 1,320: Line 1,321:
cycleSort: procedure expose array. n
cycleSort: procedure expose array. n
writes = 0
writes = 0
-- Loop through the array to find cycles to rotate.
/* Loop through the array to find cycles to rotate. */
do cycleStart=0 to n-2
do cycleStart=0 to n-2
item = array.cycleStart
item = array.cycleStart


-- Find where to put the item.
/* Find where to put the item. */
pos = cycleStart
pos = cycleStart
Do i=cycleStart+1 to n-1
Do i=cycleStart+1 to n-1
if array.i < item Then
if array.i < item Then
pos += 1
pos=pos+1
End
End


-- If the item is already there, this is not a cycle.
/* If the item is already there, this is not a cycle. */
if pos == cycleStart Then
if pos == cycleStart Then
Iterate
Iterate


-- Otherwise, put the item there or right after any duplicates.
/* Otherwise, put the item there or right after any duplicates. */
Do while item == array.pos
Do while item == array.pos
pos += 1
pos=pos+1
End
End
Parse Value array.pos item With item array.pos
Parse Value array.pos item With item array.pos
writes += 1
writes=writes+1


-- Rotate the rest of the cycle.
/* Rotate the rest of the cycle. */
Do while pos <> cycleStart
Do while pos <> cycleStart


-- Find where to put the item.
/* Find where to put the item. */
pos = cycleStart
pos = cycleStart
Do i=cycleStart + 1 to n-1
Do i=cycleStart + 1 to n-1
if array.i < item Then
if array.i < item Then
pos += 1
pos=pos+1
End
End


-- Put the item there or right after any duplicates.
/* Put the item there or right after any duplicates. */
Do while item == array.pos
Do while item == array.pos
pos += 1
pos=pos+1
End
End
Parse Value array.pos item With item array.pos
Parse Value array.pos item With item array.pos
writes += 1
writes=writes+1
End
End
End
End
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Cycle_sort"