• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Heapsort (general-purpose)

Zeda Jan 22nd, 2020 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. heapsort:
2. ;BC is the number of elements
3. ;IX points to the compare/swap routine
4.   ld a,b
5.   or c
6.   ret z
7.   push bc
8.   call heapify
9.   pop bc
10.
11. _:
12.   dec bc
13.   push bc
14.   call heap_popswap
15.   pop bc
16.   ld a,b
17.   or c
18.   jr nz,-_
19.   ret
20.
21. heap_popswap:
22.   ld hl,0
23.   call heap_swap
24.   ld h,b
25.   ld l,c
26.   xor a
27.   ld b,a
28.   ld c,a
29. heap_propogate:
30. ;If (BC+1)*2 == number of elements, then need to do check_prop_special
31. ;If (BC+1)*2 > number of elements, then we are done
32.   inc bc
33.   sbc hl,bc
34.   ret c
35.   sbc hl,bc
36.   ret c
39.   dec bc
40.   jr z,heap_check_prop_special
41.   push hl
42.   call heap_check_prop
43.   pop hl
44.   jr c,heap_propogate
45.   ret
46.
47. heap_check_prop:
48. ;returns BC as the index of the largest child
49. ;returns c flag set if still need to propogate
50. ;First, compare BC's children
51.   push bc
52.   ld h,b
53.   ld l,c
55.   inc hl
56.   ld b,h
57.   ld c,l
58.   inc hl
59.   call heap_cmp
60.   ;nc means HL is the bigger child
61.   jr c,\$+4
62.   ld b,h
63.   ld c,l
64.   pop hl
65.   push bc   ;the child node that was bigger
66.   call heap_cmp
67.   ;nc means the parent is bigger than the children, good
68.   call c,heap_swap
69.   pop bc
70.   ret
71.
72. heap_check_prop_special:
73. ;There are an even number of elements, so this parent has only one child.
74. ;We'll do a special-case heap_check_prop
75.   ld h,b
76.   ld l,c
78.   inc hl
79.   call heap_cmp
80.   ;nc means the parent is bigger than the children, good
81.   jr c,heap_swap
82.   ret
83.
84.
85. heap_swap:
86.   push bc
87.   push af
88.   scf
89.   call call_ix
90.   pop af
91.   pop bc
92.   ret
93.
94. heap_cmp:
95.   push hl
96.   push bc
97.   or a
98.   call call_ix
99.   pop bc
100.   pop hl
101.   ret
102.
103.
104. heapify:
105.   ld h,b
106.   ld l,c
107.   srl b
108.   rr c
109.   jr heapify_start
110. _:
111.   push hl
112.   push bc
113.   call heap_propogate
114.   pop bc
115.   pop hl
116. heapify_start:
117.   ld a,b
118.   or c
119.   dec bc
120.   jr nz,-_
121.   ret
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top