Sorting Algorithms/Circle Sort: Difference between revisions
Added Quackery.
m (→{{header|Phix}}: added syntax colouring the hard way) |
(Added Quackery.) |
||
Line 1,881:
print(L)
</lang>
=={{header|Quackery}}==
Having read the information on [http://sourceforge.net/p/forth-4th/wiki/Circle%20sort/ Sourceforge] mentioned in the task description, I note that the circle sort is most elegant when sorting an array the length of which is a power of two. Rather than mess with the central element of an odd length array and forego potential parallelisation I chose to pad the array to the nearest power of two with elements that were guaranteed to be in the right place (here, numbers one larger than the largest item in the array and trim it down to size after sorting. Additionally, rather than flagging exchanges, I use an O(n) test to see if a subarray is sorted to avoid unnecessary recursive calls.
The link at the end of the Sourceforge page to a paper on the subject is broken. [https://www.cscjournals.org/manuscript/Journals/IJEA/Volume6/Issue2/IJEA-48.pdf This link works.]
In the demonstration, I sort the characters in a string. In Quackery a string is a particular use of a nest of numbers (dynamic array of bignums). The string is a word from a famously circular novel. It seemed appropriate for such a novel "circle sort".
<lang Quackery> [ dup size 2 < iff
[ drop true ] done
true swap
dup [] != if
[ behead swap witheach
[ tuck > if
[ dip not
conclude ] ] ]
drop ] is sorted ( [ --> b )
[ behead swap witheach
[ 2dup < iff
nip else drop ] ] is largest ( [ --> n )
[ dup largest 1+
over size
dup 1
[ 2dup > while
1 << again ]
nip swap -
dup dip [ of join ]
swap ] is pad ( [ --> n [ )
[ swap dup if
[ negate split drop ] ] is unpad ( n [ --> [ )
[ dup size times
[ i i^ > not iff
conclude done
dup i peek
over i^ peek
2dup < iff
[ rot i poke
i^ poke ]
else 2drop ] ] is reorder ( [ --> [ )
[ pad
[ [ dup sorted if done
reorder
dup size 2 / split
recurse swap
recurse swap join ]
dup sorted until ]
unpad ] is circlesort ( [ --> [ )
$ "bababadalgharaghtakamminarronnkonnbronntonnerronntuonnthunntrovarrhounawnskawntoohoohoordenenthurnuk"
dup echo$ cr
circlesort echo$ cr</lang>
{{out}}
<pre>bababadalgharaghtakamminarronnkonnbronntonnerronntuonnthunntrovarrhounawnskawntoohoohoordenenthurnuk
aaaaaaaaaaaabbbbddeeegghhhhhhhikkkklmmnnnnnnnnnnnnnnnnnnnnnoooooooooooooorrrrrrrrrrrstttttttuuuuuvww
</pre>
=={{header|Racket}}==
| |||