Hey all, I implemented the heapsort algorithm with some features inspired by
Sean McLaughlin's implementation. Heapsort operates in O(n*log(n)) time, so it is fast even as array sizes increase. The cool perk to Sean's implementation that I wanted to include in mine is the ability to have a callback function that performs comparisons. This is fantastic if your array contains pointers to, say, an array of strings. The callback function can take the inputs (in my case, HL and DE), perform a string comparison, and return the result to the heapsort routine. Heapsort will then know whether or not to swap the elements.
As an example, I created a VAT sorting routine. It creates an array of pointers to the VAT entries of named variables (like Programs, Appvars, etc.), and then uses a fancy callback function that compares the names of the VAT entries. Returned is an alphabetically sorted array of pointers.
As well, I made a very fast routine to sort TI lists. The callback routine for this takes indices, constructs pointers to the actual list data, compares them, then returns the result. Since the OS routine uses an O(n
2) algorithm, my program can perform way faster on larger lists. I ran a few tests on random lists and came up with:
* at 100 elements, the OS routine and my routine were pretty close in speed.
* at 400 elements, my routine sorted it in ~1.3 seconds, versus ~9.5. for the OS routine
* at 999 elements, my routine sorted it in ~3.0 seconds, versus ~55.5. for the OS.
#ifndef scrap
#define scrap 8000h
.echo "Warning, 'scrap' not defined, defining scrap=8000h"
#endif
#ifndef SMC
arraybase= scrap
arraylen = scrap+2
#endif
heapflags= 33
curchild = 0
heapsort:
; HL points to the array data
; BC is the size of the array. NOT GREATER THAN 32767
; IX points to the routine that compares the values
#ifdef fast
call heapify
ld hl,(arraylen)
#else
push bc
call heapify
pop hl
#endif
_:
dec hl
ld (arraylen),hl
#ifndef fast
push hl
#endif
ld de,(arraybase)
add hl,hl
inc de
add hl,de
#ifdef fast
ld a,(de)
ldd
inc hl
ld (hl),a
dec hl
ld a,(de)
ldd
inc hl
ld (hl),a
#else
call swap
#endif
ld bc,1
call propogate
#ifdef fast
ld hl,(arraylen)
#else
pop hl
#endif
ld a,h
or l
jr nz,-_
ret
heapify:
;Inputs:
; HL points to the array data
; BC is the size of the array. NOT GREATER THAN 32767
; IX points to the routine that compares the values
ld (arraybase),hl
ld (arraylen),bc
srl b
rr c
_:
push bc
call propogate
pop bc
dec bc
ld a,b
or c
jr nz,-_
ret
propogate:
;BC-1 is the parent index
;2BC is the child1 index
res curchild,(iy+heapflags)
proppost:
sla c
rl b
ld d,b
ld e,c
#ifdef SMC
arraylen=$+1
ld hl,0
#else
ld hl,(arraylen)
#endif
sbc hl,de
add hl,de
ret c ;no children
;compare the two children
#ifdef SMC
arraybase=$+1
ld hl,0
#else
ld hl,(arraybase)
#endif
add hl,de
add hl,de
inc hl
ld d,(hl)
dec hl
ld e,(hl)
dec hl
push hl
ld a,(hl)
dec hl
ld l,(hl)
ld h,a
;HL holds the value of child0
;DE holds the value of child1
jr z,+_
call callix
jr nc,+_
ex de,hl
pop de
inc de
inc de
set curchild,(iy+heapflags)
push de
_:
;{stack} points to the child
;HL is the value of the child
;BC points to the parent
;now compare the child and parent
ex de,hl
ld hl,(arraybase)
add hl,bc
push hl
dec hl
ld a,(hl)
dec hl
ld l,(hl)
ld h,a
call callix
pop hl
pop de
ret nc
dec hl
call swap
;values swapped, now set parent=child
;BC is the index of child1
bit curchild,(iy+heapflags)
jp z,proppost
inc bc
jp propogate
swap:
;HL points to the top of one word
;DE points to the top of another
;Must preserve BC
#ifdef fast
ld a,(de)
ldd
inc hl
ld (hl),a
dec hl
ld a,(de)
ldd
inc hl
ld (hl),a
inc c
inc bc
#else
call +_
_:
ld a,(de)
ldd
inc hl
ld (hl),a
dec hl
inc bc
#endif
ret
callix:
jp (ix)
Even when optimizing for speed over size, my code is smaller, but I'm fairly sure there are more optimizations to be found!