### Author Topic: Heapsort, VATSort, and ListSort  (Read 5272 times)

0 Members and 1 Guest are viewing this topic.

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4676
• Rating: +718/-6
• Calc-u-lator, do doo doo do do do.
##### Heapsort, VATSort, and ListSort
« on: July 03, 2018, 10:29:08 pm »

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(n2) 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.

Code: (Heapsort) [Select]
#ifndef scrap#define scrap 8000h.echo "Warning, 'scrap' not defined, defining scrap=8000h"#endif#ifndef SMCarraybase= scraparraylen = scrap+2#endifheapflags= 33curchild = 0heapsort:;   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,-_        retheapify:;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,-_    retpropogate:;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 SMCarraylen=$+1 ld hl,0#else ld hl,(arraylen)#endif sbc hl,de add hl,de ret c ;no children;compare the two children#ifdef SMCarraybase=$+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 propogateswap:;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    retcallix:    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!
« Last Edit: March 28, 2020, 03:51:12 pm by Xeda112358 »

#### Eeems

• Mr. Dictator
• LV13 Extreme Addict (Next: 9001)
• Posts: 6233
• Rating: +318/-36
• little oof
##### Re: Heapsort, VATSort, and ListSort
« Reply #1 on: July 03, 2018, 11:09:27 pm »
It would be interesting if someone patched a bunch of TI-OS's commands with faster versions like this. That's pretty awesome @Xeda112358. You really need to compile a bunch of your routines into an easy to use library ;P
/e

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4676
• Rating: +718/-6
• Calc-u-lator, do doo doo do do do.
##### Re: Heapsort, VATSort, and ListSort
« Reply #2 on: July 03, 2018, 11:24:39 pm »
Haha, I have done something like that in the past. I just put a ton of my math and graphics routines into an App with a jump table to access them. Kind of like Floatlib. Really, I just need to make a Batlib 2 with my new coding techniques and methods and routines and ideas.

#### Eeems

• Mr. Dictator
• LV13 Extreme Addict (Next: 9001)
• Posts: 6233
• Rating: +318/-36
• little oof
##### Re: Heapsort, VATSort, and ListSort
« Reply #3 on: July 03, 2018, 11:35:42 pm »
I was thinking more like patching the OS so there would be no extra applications/programs/hooks installed.
/e

#### E37

• LV6 Super Member (Next: 500)
• Posts: 313
• Rating: +21/-0
• Trial and error is the best teacher
##### Re: Heapsort, VATSort, and ListSort
« Reply #4 on: July 09, 2018, 06:16:31 pm »
Ooh that would be cool. Are you allowed to post modified roms? I have a couple of my own that I could add in the extremely low chance anyone does anything about it.
I'm still around... kind of.

#### Eeems

• Mr. Dictator
• LV13 Extreme Addict (Next: 9001)
• Posts: 6233
• Rating: +318/-36
• little oof
##### Re: Heapsort, VATSort, and ListSort
« Reply #5 on: July 09, 2018, 07:25:07 pm »
Ooh that would be cool. Are you allowed to post modified roms? I have a couple of my own that I could add in the extremely low chance anyone does anything about it.
You cannot post modified roms as it contain copyrighted content.
/e

#### ibid

• LV1 Newcomer (Next: 20)
• Posts: 9
• Rating: +2/-0
##### Re: Heapsort, VATSort, and ListSort
« Reply #6 on: October 28, 2018, 03:20:43 am »
You don't need to include the rom. You could just post the patches like ThePenguin77 used to do.

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4676
• Rating: +718/-6
• Calc-u-lator, do doo doo do do do.
##### Re: Heapsort, VATSort, and ListSort
« Reply #7 on: March 28, 2020, 03:49:50 pm »
Necro Update!
I rewrote the heapsort to be really general-purpose. This significantly reduced the size of ListSort and it made it so that it doesn't require any additional user RAM (but it did make it slightly slower).

I've attached the new heapsort.z80 and listsort.z80

But then I tailored the new heapsort to the task of sorting lists and made it even smaller (200 bytes, saving 157 bytes)! And it is faster, AND this version now uses 15MHz mode if available.

Which reminds me: In the original benchmarks, I was apparently comparing my 6MHz program to TI's 15MHz SortA(, so my program is actually over 50 times faster than TI's on a 999-element list.

#### NonstickAtom785

• LV3 Member (Next: 100)
• Posts: 78
• Rating: +4/-0
• Just live life. Cal-cu-lat-or style!
##### Re: Heapsort, VATSort, and ListSort
« Reply #8 on: August 26, 2020, 10:00:44 am »
It would be interesting if someone patched a bunch of TI-OS's commands with faster versions like this. That's pretty awesome @Xeda112358. You really need to compile a bunch of your routines into an easy to use library ;P

I like this idea. I've thought about what it would be like to have a run hook that takes every BASIC Command and converts it so that it goes way faster. So an interpreter for an interpreter pretty much. It would be so much more quicker!
Grammer2 is Good!