Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
(Added Quackery) |
|||
Line 3,991: | Line 3,991: | ||
>>> heapsort(ary) |
>>> heapsort(ary) |
||
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</pre> |
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</pre> |
||
=={{header|Quackery}}== |
|||
<lang Quackery> |
|||
[ stack ] is pq ( [ --> [ ) |
|||
[ pq share swap peek ] is pq.peek ( n --> x ) |
|||
[ pq take swap poke pq put ] is pq.poke ( n x --> ) |
|||
[ 1+ 2 / 1 - ] is parent ( n --> n ) |
|||
[ 0 > ] is has-parent ( n --> b ) |
|||
[ 2 * 1+ ] is child ( n --> n ) |
|||
[ child pq share size < ] is has-child ( n --> b ) |
|||
[ 1+ ] is sibling ( n --> n ) |
|||
[ sibling pq share size < ] is has-sibling ( n --> b ) |
|||
[ stack ] is comparison ( [ --> [ ) |
|||
[ comparison share do ] is pq.compare ( x x --> b ) |
|||
[ over size |
|||
rot 0 join pq put |
|||
[ dup has-parent while |
|||
dup parent |
|||
rot over pq.peek |
|||
2dup pq.compare iff |
|||
[ 2swap unrot pq.poke ] |
|||
again |
|||
rot 2drop swap ] |
|||
pq.poke pq take ] is toheap ( h x --> h ) |
|||
( toheap is not used in the heapsort, but |
|||
completes the set of heap operations ) |
|||
[ dup pq.peek swap |
|||
[ dup has-child while |
|||
dup child |
|||
dup has-sibling if |
|||
[ dup sibling pq.peek |
|||
over pq.peek |
|||
pq.compare if sibling ] |
|||
dip over dup pq.peek |
|||
rot dip dup pq.compare iff |
|||
[ rot pq.poke ] |
|||
again |
|||
2drop ] |
|||
pq.poke ] is pq.heapify ( n --> ) |
|||
[ behead |
|||
over [] = if done |
|||
swap -1 split |
|||
swap join pq put |
|||
0 pq.heapify |
|||
pq take swap ] is fromheap ( h --> h v ) |
|||
[ dup pq put |
|||
size 2 / times |
|||
[ i pq.heapify ] |
|||
pq take ] is makeheap ( [ --> h ) |
|||
[ ]'[ comparison put |
|||
[] swap makeheap |
|||
dup size times |
|||
[ fromheap |
|||
nested rot join |
|||
swap ] |
|||
drop |
|||
comparison release ] is hsortwith ( [ --> [ ) |
|||
[ hsortwith > ] is hsort ( [ --> [ ) |
|||
[] 23 times [ 90 random 10 + join ] |
|||
say " " dup echo cr |
|||
say " --> " hsort echo </lang> |
|||
''' Output:''' |
|||
<pre> [ 71 62 11 25 15 19 87 91 62 73 89 81 39 12 35 20 25 72 76 20 88 73 82 ] |
|||
--> [ 11 12 15 19 20 20 25 25 35 39 62 62 71 72 73 73 76 81 82 87 88 89 91 ] |
|||
</pre> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |