Wow, this is pretty cool. With just this description, I developed my first correctly working heapsort! And the rest of the related algorithms come easily (at least how I worked them in my mind) and they are super fast.
edit: Super fast in a computational efficiency way, not in a TI-BASIC implementation way :P
Join Heaps:
Inputs: L1=(almost) heap, K=offset, N=number of elements of the heap
This code essentially assumes that starting at leaf K, it's sub-trees are all heaps. This joins those sub-trees with K at the head, then it properly reorganizes so that the entire thing is once again a heap.
This code allows us to recursively build a heap from the bottom up, while doing it efficiently.
K→C
Ans2→B
While B≤N
If B<N
Then
If L1(B)<L1(B+1
B+1→B
End
If L1(B)>L1(C
Then
L1(B→A
L1(C→L1(B
A→L1(C
End
B→C
B2→B
End
Heapify:
This code take input as Ans and L1. The first 'Ans' elements of L1 are converted into a heap structure.
Ans→N
If Ans<2
Return
1
While Ans2≤N
Ans2
End
Ans-1→D
For K,D,1,-1
prgmHEAPJOIN
End
Heapsort:
This takes L1 as a list, and Ans as the number of elements to sort. This then sorts from least to greatest.
prgmHEAPIFY
N→M
For(I,0,M-1
L1(M-I→A
L1(1→L1(M-I
A→L1(1
1→K
N-1→N
prgmHEAPJOIN
End
This heapsort routine isn't very useful for TI-BASIC, but it's fun for demonstration :)
Z80 Assembly>English>TI-BASIC>Python>French>C>0