Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
m (→{{header|Quackery}}: typo) |
(→{{header|Quackery}}: revamped) |
||
Line 4,413: | Line 4,413: | ||
=={{header|Quackery}}== |
=={{header|Quackery}}== |
||
⚫ | |||
⚫ | |||
This uses code from [[Priority queue#Quackery]]' |
|||
[ 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 |
|||
⚫ | |||
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 x ) |
|||
[ dup pq put |
|||
⚫ | |||
[ 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 ] |
[] 23 times [ 90 random 10 + join ] |
||
say " " dup echo cr |
say " " dup echo cr |
||
Line 4,492: | Line 4,426: | ||
''' Output:''' |
''' Output:''' |
||
<pre> [ |
<pre> [ 45 82 25 50 14 45 11 25 21 91 10 63 77 42 80 99 16 81 88 97 84 80 87 ] |
||
--> [ 11 |
--> [ 10 11 14 16 21 25 25 42 45 45 50 63 77 80 80 81 82 84 87 88 91 97 99 ]</pre> |
||
</pre> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |