; ===================================================== ; Atari 130XE HeapSort ; First-pass implementation ; ; Signed 16-bit integers ; Array element size = 2 bytes ; ===================================================== ARRAY = $4000 ; ----------------------------------------------------- ; Zero Page ; ----------------------------------------------------- PTR1 = $80 PTR1H = $81 PTR2 = $82 PTR2H = $83 ROOTL = $84 ROOTH = $85 CHILDL = $86 CHILDH = $87 ENDL = $88 ENDH = $89 COUNTL = $8A COUNTH = $8B INDEXL = $8C INDEXH = $8D TEMPLO = $8E TEMPHI = $8F ; --------------------------------------------------------------------------- ; HeapSort ; Purpose: ; Build a max heap, then sort ARRAY in place in ascending order. ; Parameters: ; COUNTL/COUNTH - 16-bit element count; input values are signed 16-bit. ; Returns: ; None; sorted values remain in ARRAY. ; Variables/registers used: ; ROOT, END, INDEX, PTR1/PTR2, CHILD, TEMP - zero-page heap and pointer state. ; A, X, Y, flags - scratch registers and branch status. ; --------------------------------------------------------------------------- HeapSort ; start = count / 2 lda COUNTH lsr sta ROOTH lda COUNTL ror sta ROOTL ; start-- lda ROOTL bne HS1 dec ROOTH HS1 dec ROOTL ; ===================================================== ; Build Heap ; ===================================================== BuildHeap lda ROOTH bmi BuildDone jsr SiftDown lda ROOTL bne BHDec lda ROOTH beq BuildDone BHDec sec lda ROOTL sbc #1 sta ROOTL lda ROOTH sbc #0 sta ROOTH jmp BuildHeap BuildDone lda COUNTL sta ENDL lda COUNTH sta ENDH sec lda ENDL sbc #1 sta ENDL lda ENDH sbc #0 sta ENDH ; ===================================================== ; Extraction Loop ; ===================================================== SortLoop lda ENDL ora ENDH beq SortDone ; swap root and end lda #0 sta INDEXL sta INDEXH jsr GetPtr1 lda ENDL sta INDEXL lda ENDH sta INDEXH jsr GetPtr2 jsr Swap16 ; root = 0 lda #0 sta ROOTL sta ROOTH jsr SiftDownEnd ; end-- sec lda ENDL sbc #1 sta ENDL lda ENDH sbc #0 sta ENDH jmp SortLoop SortDone rts ; --------------------------------------------------------------------------- ; SiftDown ; Purpose: ; Restore the max-heap property below ROOT using COUNT as the heap end. ; Parameters: ; ROOTL/ROOTH - zero-based root index; COUNTL/COUNTH - element count. ; Returns: ; None; updates ARRAY in place. ; Variables/registers used: ; END, CHILD, INDEX, PTR1/PTR2, TEMP - zero-page scratch; A, Y, flags. ; --------------------------------------------------------------------------- SiftDown lda COUNTL sta ENDL lda COUNTH sta ENDH ; --------------------------------------------------------------------------- ; SiftDownEnd ; Purpose: ; Continue SiftDown with an explicitly supplied exclusive heap end. ; Parameters: ; ROOTL/ROOTH and ENDL/ENDH - zero-based root and exclusive heap end. ; Returns: ; None; updates ARRAY in place and returns through SDDone. ; Variables/registers used: ; CHILD, INDEX, PTR1/PTR2, TEMP - zero-page scratch; A, Y, flags. ; --------------------------------------------------------------------------- SiftDownEnd SDLoop ; child = root*2 + 1 lda ROOTL asl sta CHILDL lda ROOTH rol sta CHILDH inc CHILDL bne SD1 inc CHILDH SD1 ; child >= end ? lda CHILDH cmp ENDH bcc ChildValid bne SDDone lda CHILDL cmp ENDL bcs SDDone ChildValid ; choose larger child jsr SelectLargestChild ; compare root and child jsr CompareRootChild bcs SDDone jsr SwapRootChild lda CHILDL sta ROOTL lda CHILDH sta ROOTH jmp SDLoop SDDone rts ; --------------------------------------------------------------------------- ; SelectLargestChild ; Purpose: ; Select the larger valid child and store its index in CHILD. ; Parameters: ; CHILD - left-child index; END - exclusive heap end. ; Returns: ; None; updates CHILD and uses carry from ChildVsRight for selection. ; Variables/registers used: ; INDEX - candidate right child; A and flags - index comparison state. ; --------------------------------------------------------------------------- SelectLargestChild lda CHILDL clc adc #1 sta INDEXL lda CHILDH adc #0 sta INDEXH ; right child >= end ? lda INDEXH cmp ENDH bcc SC1 bne SCSkip lda INDEXL cmp ENDL bcs SCSkip SC1 jsr ChildVsRight bcs SCSkip lda INDEXL sta CHILDL lda INDEXH sta CHILDH SCSkip rts ; --------------------------------------------------------------------------- ; CompareRootChild ; Purpose: ; Compare ARRAY[ROOT] with ARRAY[CHILD] as signed 16-bit values. ; Parameters: ; ROOT, CHILD - zero-based indices in zero page. ; Returns: ; Carry set when ARRAY[ROOT] >= ARRAY[CHILD]. ; Variables/registers used: ; INDEX, PTR1/PTR2 - pointer construction; A, Y, flags - comparison state. ; --------------------------------------------------------------------------- CompareRootChild lda ROOTL sta INDEXL lda ROOTH sta INDEXH jsr GetPtr1 lda CHILDL sta INDEXL lda CHILDH sta INDEXH jsr GetPtr2 jmp Compare16Signed ; --------------------------------------------------------------------------- ; SwapRootChild ; Purpose: ; Exchange ARRAY[ROOT] and ARRAY[CHILD]. ; Parameters: ; ROOT, CHILD - zero-based indices in zero page. ; Returns: ; None; updates ARRAY in place. ; Variables/registers used: ; INDEX, PTR1/PTR2, TEMP - pointer and swap scratch; A, Y. ; --------------------------------------------------------------------------- SwapRootChild lda ROOTL sta INDEXL lda ROOTH sta INDEXH jsr GetPtr1 lda CHILDL sta INDEXL lda CHILDH sta INDEXH jsr GetPtr2 jmp Swap16 ; --------------------------------------------------------------------------- ; GetPtr1 ; Purpose: ; Build the byte address ARRAY + index*2 in PTR1/PTR1H. ; Parameters: ; INDEXL/INDEXH - zero-based array index. ; Returns: ; Pointer in PTR1/PTR1H. ; Variables/registers used: ; PTR1/PTR1H, A, carry flag. ; --------------------------------------------------------------------------- GetPtr1 lda INDEXL asl sta PTR1 lda INDEXH rol sta PTR1H clc lda PTR1 adc #ARRAY sta PTR1H rts ; --------------------------------------------------------------------------- ; GetPtr2 ; Purpose: ; Build the byte address ARRAY + index*2 in PTR2/PTR2H. ; Parameters: ; INDEXL/INDEXH - zero-based array index. ; Returns: ; Pointer in PTR2/PTR2H. ; Variables/registers used: ; PTR2/PTR2H, A, carry flag. ; --------------------------------------------------------------------------- GetPtr2 lda INDEXL asl sta PTR2 lda INDEXH rol sta PTR2H clc lda PTR2 adc #ARRAY sta PTR2H rts ; --------------------------------------------------------------------------- ; Swap16 ; Purpose: ; Exchange the two 16-bit values addressed by PTR1 and PTR2. ; Parameters: ; PTR1/PTR1H and PTR2/PTR2H - addresses of the values. ; Returns: ; None; updates both memory locations. ; Variables/registers used: ; TEMPLO/TEMPHI - byte swap storage; A, Y. ; --------------------------------------------------------------------------- Swap16 ldy #0 lda (PTR1),y sta TEMPLO lda (PTR2),y sta (PTR1),y lda TEMPLO sta (PTR2),y iny lda (PTR1),y sta TEMPHI lda (PTR2),y sta (PTR1),y lda TEMPHI sta (PTR2),y rts ; --------------------------------------------------------------------------- ; Compare16Signed ; Purpose: ; Compare the signed 16-bit values addressed by PTR1 and PTR2. ; Parameters: ; PTR1/PTR1H - left value; PTR2/PTR2H - right value. ; Returns: ; Carry set when the left value is greater than or equal to the right. ; Variables/registers used: ; A, Y and processor flags; pointer pairs remain unchanged. ; --------------------------------------------------------------------------- Compare16Signed ldy #1 lda (PTR1),y eor (PTR2),y bmi DifferentSigns lda (PTR1),y cmp (PTR2),y bne HighDone dey lda (PTR1),y cmp (PTR2),y rts HighDone rts DifferentSigns lda (PTR1),y bmi AGreater clc rts AGreater sec rts ; =====================================================