Sorting algorithms/Cycle sort: Difference between revisions

Content added Content deleted
(Added Elixir)
m (→‎{{header|REXX}}: changed/added comments and whitespace, changed indentations.)
Line 1,023: Line 1,023:


As a default, the program uses (for the input list) some digits of pi, which for practical purposes, appear random.
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. */
<lang rexx>/*REXX program demonstrates a cycle sort on a list of items. */
parse arg z /* [↓] not specified? Use π digs*/
parse arg z /* [↓] not specified? Use "pi" digits.*/
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
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 #s. */
say 'unsorted list: ' z /*show the original unsorted numbers. */
w=sortCycle(z) /*W: the # of writes done in sort*/
w=sortCycle(z) /*W: the number of writes done in sort*/
say 'and took' w 'writes.' /*show # of writes done in sort. */
say 'and took' w 'writes.' /*show number of writes done in sort. */
exit /*stick a fork in it, we're done.*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────SORTCYCLE subroutine────────────────*/
sortCycle: procedure expose @.; parse arg y; #=words(y); writes=0
sortCycle: procedure expose @.; parse arg y; #=words(y); writes=0
do i=1 for #; @.i=word(y,i); end /*i*/ /*put items ───► @.*/
do i=1 for #; @.i=word(y,i); end /*i*/ /*put each of the items ───► @. array.*/
/* [↓] find cycles to rotate. */
/* [↓] find a "cycle" to rotate. */
do c=1 for #; x=@.c; p=c /*X is the item being sorted. */
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 /*where to put X.*/
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? This ain't a cycle*/
if p==c then iterate /*Is it there? No, this ain't a cycle.*/
do while x==@.p; p=p+1; end /*put X right after any duplicate*/
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.*/
parse value @.p x with x @.p /*swap the two values: @.p and X.*/
writes=writes+1 /*bump counter for # of writes.*/
writes=writes+1 /*bump counter for the number of writes*/
do while p\==c; p=c /*rotate the rest of the cycle. */
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 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.*/
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.*/
parse value @.p x with x @.p /*swap the two values: @.p and X.*/
writes=writes+1 /*bump counter for # of writes.*/
writes=writes+1 /*bump the counter for number of writes*/
end /*while p\==c*/
end /*while p\==c*/
end /*c*/
end /*c*/
/* [↓] display the sorted list. */
/* [↓] display the sorted list. */
_=@.1; do j=2 to #; _=_ @.j; end; say ' sorted list: ' _
_=@.1; do j=2 to #; _=_ @.j; end; say ' sorted list: ' _
return writes</lang>
return writes</lang>
{{out}} using the default input:
'''output''' &nbsp; when using the default input:
<pre>
<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
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: Line 1,056:
and took 34 writes.
and took 34 writes.
</pre>
</pre>
{{out}} using the input of: &nbsp; <tt> FM Stereo has been around since 1961. </tt>
'''output''' &nbsp; when using the input of: &nbsp; <tt> FM Stereo has been around since 1961. </tt>
<pre>
<pre>
unsorted list: FM Stereo has been around since 1961.
unsorted list: FM Stereo has been around since 1961.
Line 1,069: Line 1,069:
===version 3===
===version 3===
This version uses a faster (but a more cryptic) version of incrementing &nbsp; '''1''' &nbsp; (one) to &nbsp; '''P''' &nbsp; within two '''do''' loops.
This version uses a faster (but a more cryptic) version of incrementing &nbsp; '''1''' &nbsp; (one) to &nbsp; '''P''' &nbsp; within two '''do''' loops.
<lang rexx>/*REXX program demonstrates a cycle sort on a list of items. */
<lang rexx>/*REXX program demonstrates a cycle sort on a list of items. */
parse arg z /* [↓] not specified? Use π digs*/
parse arg z /* [↓] not specified? Use "pi" digits.*/
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
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 #s. */
say 'unsorted list: ' z /*show the original unsorted numbers. */
w=sortCycle(z) /*W: the # of writes done in sort*/
w=sortCycle(z) /*W: the number of writes done in sort*/
say 'and took' w 'writes.' /*show # of writes done in sort. */
say 'and took' w 'writes.' /*show number of writes done in sort. */
exit /*stick a fork in it, we're done.*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────SORTCYCLE subroutine────────────────*/
sortCycle: procedure expose @.; parse arg y; #=words(y); writes=0
sortCycle: procedure expose @.; parse arg y; #=words(y); writes=0
do i=1 for #; @.i=word(y,i); end /*i*/ /*put items ───► @.*/
do i=1 for #; @.i=word(y,i); end /*i*/ /*put each of the items ───► @. array.*/
/* [↓] find cycles to rotate. */
/* [↓] find a "cycle" to rotate. */
do c=1 for #; x=@.c; p=c /*X is the item being sorted. */
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 /*where to put X.*/
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? This ain't a cycle*/
if p==c then iterate /*Is it there? No, this ain't a cycle.*/
do p=p while x==@.p; end /*put X right after any duplicate*/
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.*/
parse value @.p x with x @.p /*swap the two values: @.p and X.*/
writes=writes+1 /*bump counter for # of writes. */
writes=writes+1 /*bump counter for the number of writes*/
do while p\==c; p=c /*rotate the rest of the cycle. */
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 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.*/
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.*/
parse value @.p x with x @.p /*swap the two values: @.p and X.*/
writes=writes+1 /*bump counter for # of writes.*/
writes=writes+1 /*bump the counter for number of writes*/
end /*while p\==c*/
end /*while p\==c*/
end /*c*/
end /*c*/
/* [↓] display the sorted list. */
/* [↓] display the sorted list. */
_=@.1; do j=2 to #; _=_ @.j; end; say ' sorted list: ' _
_=@.1; do j=2 to #; _=_ @.j; end; say ' sorted list: ' _
return writes</lang>
return writes</lang>
Line 1,100: Line 1,100:
===version 4===
===version 4===
This version uses a subroutine to perform the task of handling an (sorted) item placement (possibly after duplicates).
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. */
<lang rexx>/*REXX program demonstrates a cycle sort on a list of items. */
parse arg z /* [↓] not specified? Use π digs*/
parse arg z /* [↓] not specified? Use "pi" digits.*/
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
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 #s. */
say 'unsorted list: ' z /*show the original unsorted numbers. */
w=sortCycle(z) /*W: the # of writes done in sort*/
w=sortCycle(z) /*W: the number of writes done in sort*/
say 'and took' w 'writes.' /*show # of writes done in sort. */
say 'and took' w 'writes.' /*show number of writes done in sort. */
exit /*stick a fork in it, we're done.*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────SORTCYCLE subroutine────────────────*/
sortCycle: procedure expose @.; parse arg y; #=words(y); w=0
sortCycle: procedure expose @.; parse arg y; #=words(y); w=0
do i=1 for #; @.i=word(y,i); end /*i*/ /*put items───►@.*/
do i=1 for #; @.i=word(y,i); end /*i*/ /*put each of the items ───► @. array.*/


do c=1 for #; x=@.c; p=c /*X is the item being sorted. */
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*/
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? This ain't a cycle*/
if p==c then iterate /*Is it there? Then this ain't a cycle*/
call .swap /*put X here or right after dups.*/
call .swap /*put X here or right after dups.*/
do while p\==c; p=c /*rotate the rest of the cycle. */
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 k=c+1 to #; if @.k<x then p=p+1; end /*k*/
call .swap /*put X here or right after dups.*/
call .swap /*put X here or right after dups.*/
end /*while p\==c*/
end /*while p\==c*/
end /*c*/
end /*c*/
/* [↓] display the sorted list. */
/* [↓] display the sorted list. */
_=@.1; do j=2 to #; _=_ @.j; end; say ' sorted list: ' _
_=@.1; do j=2 to #; _=_ @.j; end; say ' sorted list: ' _
return w /* [↓] find where to put X into @*/
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>
.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.
'''output''' &nbsp; is identical to the 2<sup>nd</sup> version.


=={{header|Ruby}}==
=={{header|Ruby}}==
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Cycle_sort"