Anonymous user
Sorting algorithms/Cycle sort: Difference between revisions
m
→{{header|REXX}}: changed/added comments and whitespace, changed indentations.
(Added Elixir) |
m (→{{header|REXX}}: changed/added comments and whitespace, changed indentations.) |
||
Line 1,023:
As a default, the program uses (for the input list) some digits of pi, which for practical purposes, appear random.
<lang rexx>/*REXX program demonstrates a cycle sort on a list of items. */
parse arg z /* [↓] not specified? Use
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
w=sortCycle(z) /*W: the
say 'and took' w 'writes.' /*show
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
sortCycle: procedure expose @.; parse arg y; #=words(y); writes=0
do i=1 for #; @.i=word(y,i); end /*i*/
/* [↓] find
do c=1 for #; x=@.c; p=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. */
if p==c then iterate /*Is it there?
do while x==@.p; p=p+1; end /*put X right after any duplicate. */
parse value @.p x with x @.p /*swap the two values: @.p and X.*/
writes=writes+1 /*bump counter for the
do while p\==c; p=c /*rotate the rest of the "cycle". */
do k=c+1 to #; if @.k<x then p=p+1; end /*k*/
do while x==@.p; p=p+1; end /*put X here or right after dups. */
parse value @.p x with x @.p /*swap the two values: @.p and X.*/
writes=writes+1 /*bump the counter for
end /*while p\==c*/
end /*c*/
/* [↓] display the sorted list. */
_=@.1; do j=2 to #; _=_ @.j; end; say ' sorted list: ' _
return writes</lang>
<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
Line 1,056:
and took 34 writes.
</pre>
<pre>
unsorted list: FM Stereo has been around since 1961.
Line 1,069:
===version 3===
This version uses a faster (but a more cryptic) version of incrementing '''1''' (one) to '''P''' within two '''do''' loops.
<lang rexx>/*REXX program demonstrates a cycle sort on a list of items. */
parse arg z /* [↓] not specified? Use
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
w=sortCycle(z) /*W: the
say 'and took' w 'writes.' /*show
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
sortCycle: procedure expose @.; parse arg y; #=words(y); writes=0
do i=1 for #; @.i=word(y,i); end /*i*/
/* [↓] find
parse
writes=writes+1 /*bump counter for the
do while p\==c; p=c /*rotate the rest of the "cycle". */
do k=c+1 to #; if @.k<x then p=p+1; end /*k*/
do p=p while x==@.p; end /*put X here or right after dups.*/
parse value @.p x with x @.p /*swap the two values: @.p and X.*/
writes=writes+1 /*bump the counter for
end /*while p\==c*/
end /*c*/
/* [↓] display the sorted list. */
_=@.1; do j=2 to #; _=_ @.j; end; say ' sorted list: ' _
return writes</lang>
Line 1,100:
===version 4===
This version uses a subroutine to perform the task of handling an (sorted) item placement (possibly after duplicates).
<lang rexx>/*REXX program demonstrates a cycle sort on a list of items. */
parse arg z /* [↓] not specified? Use
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
w=sortCycle(z) /*W: the
say 'and took' w 'writes.' /*show
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
sortCycle: procedure expose @.; parse arg y; #=words(y); w=0
do c=1 for #; x=@.c; p=c /*X is the item being sorted. */
do j=c+1 to #; if @.j<x then p=p+1; end /*j*/ /*where to put X.*/
if p==c then iterate /*Is it there?
call .swap /*put X here or right after dups.*/
do while p\==c; p=c /*rotate the rest of the "cycle". */
do k=c+1 to #; if @.k<x then p=p+1; end /*k*/
call .swap /*put X here or right after dups.*/
end /*while p\==c*/
end /*c*/
/* [↓] display the sorted list. */
_=@.1; do j=2 to #; _=_ @.j; end;
return w /* [↓] find where to put X into @*/
.swap: do p=p while x==@.p; end; parse value @.p x with x @.p; w=w+1; return</lang>
'''output''' is identical to the 2<sup>nd</sup> version.
=={{header|Ruby}}==
|