Sorting algorithms/Cycle sort: Difference between revisions
Content added Content deleted
(Add NetRexx) |
Walterpachl (talk | contribs) (→REXX version 1: corrected) |
||
| Line 581: | Line 581: | ||
<lang rexx>/* REXX *************************************************************** |
<lang rexx>/* REXX *************************************************************** |
||
* 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) |
|||
**********************************************************************/ |
**********************************************************************/ |
||
list='1 9 3 5 8 4 7 0 6 2' |
list='1 9 3 5 8 4 7 0 6 2' |
||
| Line 588: | Line 589: | ||
End |
End |
||
Say list |
Say list |
||
writes=cyclesort() |
|||
Say 'writes='writes |
|||
ol='' |
ol='' |
||
Do i=0 To n-1 |
Do i=0 To n-1 |
||
| Line 596: | Line 598: | ||
Exit |
Exit |
||
cycleSort: |
cycleSort: procedure expose array. n |
||
writes = 0 |
writes = 0 |
||
-- Loop through the array to find cycles to rotate. |
|||
do cycleStart=0 to n- |
do cycleStart=0 to n-2 |
||
item = array.cycleStart |
item = array.cycleStart |
||
-- Find where to put the item. |
|||
pos = cycleStart |
pos = cycleStart |
||
Do i=cycleStart to n |
Do i=cycleStart+1 to n-1 |
||
if array.i < item Then |
if array.i < item Then |
||
pos += 1 |
pos += 1 |
||
End |
End |
||
-- 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. |
|||
Do while item == array.pos |
Do while item == array.pos |
||
pos += 1 |
pos += 1 |
||
| Line 612: | Line 621: | ||
Parse Value array.pos item With item array.pos |
Parse Value array.pos item With item array.pos |
||
writes += 1 |
writes += 1 |
||
-- Rotate the rest of the cycle. |
|||
Do while pos <> cycleStart |
Do while pos <> cycleStart |
||
-- Find where to put the item. |
|||
pos = cycleStart |
pos = cycleStart |
||
Do i=cycleStart + 1 to n |
Do i=cycleStart + 1 to n-1 |
||
if array.i < item Then |
if array.i < item Then |
||
pos += 1 |
pos += 1 |
||
End |
End |
||
-- Put the item there or right after any duplicates. |
|||
Do while item == array.pos |
Do while item == array.pos |
||
pos += 1 |
pos += 1 |
||
| Line 625: | Line 640: | ||
End |
End |
||
End |
End |
||
return writes</lang> |
|||
return</lang> |
|||
{{out}} |
{{out}} |
||
<pre>1 9 3 5 8 4 7 0 6 2 |
<pre>1 9 3 5 8 4 7 0 6 2 |
||