Rosetta Code

Sorting algorithms/Cycle sort: Difference between revisions

Page Discussion

Sorting algorithms/Cycle sort (view source)

Revision as of 18:17, 21 May 2020

146 bytes added ,  4 years ago
m
→‎version 2: added/changed comments and whitespace, use a subroutine for common code, used a template for the output.
(Added Wren)
m (→‎version 2: added/changed comments and whitespace, use a subroutine for common code, used a template for the output.)
Line 1,570:
 
===version 2===
This REXX version demonstrates the use of negative numbers and non-integeralso non─integer values in the list.
 
As a default, the program uses (for the input list) some digits of pi, which for practical purposes, appear random.
<lang rexx>/*REXX program demonstratesperforms a cycle sort on a list of items. (could be numbers or text).*/
parse arg z /*obtain [↓]optional notarguments specified?from the Use "pi" digits.CL*/
if z='' then z= -3.14 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4
say 'unsorted list: ' z /*show the original unsorted numbers. */
w= sortCycle(z) /*W: the number of writes done in sort*/
say 'and took sorted list: ' wy "writes." /*show number of writesthe doneoriginal inunsorted sortnumbers. */
say 'and required ' w " writes." /*show number of writes done in sort. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
sortCycle: procedure expose @.y; parse arg y; #= words(y); mv= 0 /*MV: #=words(y); moves or writes=0*/
do i=1 for #; @.i= word(y,i); end /*i*/ /*put each of the items ───► @. array.*/
end /*i*/ /* [↓] find a "cycle" to rotate. */
do c=1 for #; x=@.c; p=c c /*X is the item being sorted. */
do j=c+1 to #; if @.j<x then p= p + 1; end /*determine where to put X. into array @*/
end /*while p\==cj*/▼
if p==c then iterate /*Is it there? No, this ain't a cycle.*/
if p==c then iterate do while x==@.p; p=p+1; end /*put X right after any/*Is duplicate.it there? No, this ain't a cycle.*/
parsecall value.putX @.p x with x @.p /*swap the two values: @.p and /*put X right after any dups; swap. */
writes=writes+1 do while p\==c; p= c /*bumprotate counterthe forrest of the number"cycle". of writes*/
do while p\==c; do pk=c+1 to #; if @.k<x then p= p+1 /*rotatedetermine thewhere restto ofput thethis "cycle"element. */
do k=c+1end to #; if @.k<x then p=p+1; end /*k*/
call .putX do while x==@.p; p=p+1; end /*put X here or /*put X right after any dups.; swap. */
end /*while p\==c*/
parse value @.p x with x @.p /*swap the two values: @.p and X.*/
writes=writes+1 /*bump the counter for number of writes*/
▲ end /*while p\==c*/
end /*c*/
_y=@.1; do jm=2 tofor #-1; _y=_y @.jm; end; return mv /*put the array back sayinto 'the sortedY list: ' _list.*/▼
/* [↓] display the sorted list. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
▲_=@.1; do j=2 to #; _=_ @.j; end; say ' sorted list: ' _
.putX: mv= mv+1; do p=p while x==@.p; end; parse value @.p x with x @.p; return</lang>
return writes</lang>
'''{{out|output''' |text=&nbsp; when using the default input:}}
<pre>
unsorted list: -3.14 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4
sorted list: -3.14 0 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 7 7 8 8 8 8 8 9 9 9 9
and tookrequired 34 writes.
</pre>
'''{{out|output''' |text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> FM Stereo has been around since 1961. </tt>}}
<pre>
unsorted list: FM Stereo has been around since 1961.
sorted list: 1961. FM Stereo around been has since
and tookrequired 7 writes.
</pre>
Note (for the above output). &nbsp; This REXX program was executed on an '''ASCII''' machine.
<br>On an &nbsp; '''ASCII''' &nbsp; machine, the order of sorting is numbers, uppercase letters, lowercase letters.<br>
On an '''EBCDIC''' machine, the order of sorting is lowercase letters, uppercase letters, numbers.<br>
Other (special) characters may also be in a different order. <br><br>
 
===version 3===
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/247956"