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
  37.   add hl,bc
  38.   add hl,bc
  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
  54.   add hl,hl
  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
  77.   add hl,hl
  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. OK, I Understand
Top