User Tools

Site Tools


base:bubble_sort_16-bit_elements

Bubble Sort (for 16-Bit Elements)

from 6502 Software Design

Sorting Lists Having 16-Bit Elements

The sort subroutine discussed in the preceding example (see 8-bit Bubble Sort) was relatively simple because the elements were 8-bit values, and could be compared with a CMP instruction and exchanged without too much difficulty. Unfortunately, the 6502 microprocessor has no 16-bit compare instruction, so a comparison must be made by actually subtracting the elements and testing the status of the result; if a borrow occurs, the elements must be exchanged, otherwise the elements can remain in their present order. The SORT16 subroutine sorts 16-bit elements using the bubble-sort algorithm and a 16-bit “compare” sequence.

;THIS SUBROUTINE ARRANGES THE 16-BIT ELEMENTS OF A LIST IN
;ASCENDING ORDER.  THE STARTING ADDRESS OF THE LIST IS IN LOCATIONS
;$30 AND $31.  THE LENGTH OF THE LIST IS IN THE FIRST BYTE OF THE LIST.
;LOCATION $32 IS USED TO HOLD AN EXCHANGE FLAG.

SORT16   LDY #$00     ;TURN EXCHANGE FLAG OFF (= 0)
         STY $32
         LDA ($30),Y  ;FETCH ELEMENT COUNT
         TAY          ;  AND USE IT TO INDEX LAST ELEMENT
NXTEL    LDA ($30),Y  ;FETCH MSBY
         PHA          ;  AND PUSH IT ONTO STACK
         DEY
         LDA ($30),Y  ;FETCH LSBY
         SEC
         DEY
         DEY
         SBC ($30),Y  ; AND SUBTRACT LSBY OF PRECEDING ELEMENT
         PLA
         INY
         SBC ($30),Y  ; AND SUBTRACT MSBY OF PRECEDING ELEMENT
         BCC SWAP     ;ARE THESE ELEMENTS OUT OF ORDER?
         CPY #$02     ;NO. LOOP UNTIL ALL ELEMENTS COMPARED
         BNE NXTEL
         BIT $32      ;EXCHANGE FLAG STILL OFF?
         BMI SORT16   ;NO. GO THROUGH LIST AGAIN
         RTS

;THIS ROUTINE BELOW EXCHANGES TWO 16-BIT ELEMENTS IN MEMORY

SWAP     LDA ($30),Y  ;SAVE MSBY1 ON STACK
         PHA
         DEY
         LDA ($30),Y  ;SAVE LSBY1 ON STACK
         PHA
         INY
         INY
         INY
         LDA ($30),Y  ;SAVE MSBY2 ON STACK
         PHA
         DEY
         LDA ($30),Y  ;LOAD LSBY2 INTO ACCUMULATOR
         DEY
         DEY
         STA ($30),Y  ; AND STORE IT AT LSBY1 POSITION
         LDX #$03
SLOOP    INY          ;STORE THE OTHER THREE BYTES
         PLA
         STA ($30),Y
         DEX
         BNE SLOOP    ;LOOP UNTIL THREE BYTE STORED
         LDA #$FF     ;TURN EXCHANGE FLAG ON (= -1)
         STA $32
         CPY #04      ;WAS EXCHANGE DONE AT START OF LIST?
         BEQ SORT16   ;YES. GO THROUGH LIST AGAIN.
         DEY          ;NO. COMPARE NEXT ELEMENT PAIR
         DEY
         JMP NXTEL

The SORT16 subroutine is designed with the same algorithm as SORT8, so the two subroutines have several characteristics in common. For example, both SORT8 and SORT16 have an exchange flag (in the same location, $32) that indicates whether or not an exchange occurred during the last pass through the list. Like SORT8, the SORT16 subroutine also compares adjacent elements (albeit with a 16-bit subtraction, as opposed to the simple 8-bit comparison of the SORT8) and has an exchange routine that interchanges misordered elements in memory.

Aside from the fact that SORT8 and SORT16 operate on different size elements, the only other real difference between them is that SORT16 processes the list from the end and works upward, whereas, SORT8 process the list from the beginning and works downward. Why the difference in procedure? There is no good reason, other than to demonstrate that a bubble sort can operate in either direction.

SORT16 starts by initializing the exchange flag to zero, and fetching the element count from the first byte of the list. Using that value to point Y at the last element, the 6502 microprocessor executes “compare” (subtraction) instructions. These instructions, which start with the NXTEL instruction, perform a double-precision subtraction. In this subtraction, the lest-significant bytes (LSBYs) are subtracted first, and any borrow from that operation is passed, via the Carry, to the subtraction of the most-significant bytes (MSBYs).

Operations on multiple-precision elements typically require a lot of pointer manipulation, as you can see by the instructions that follow the NXTEL label. To get the higher-addressed LSBY, the Y register must be decremented from its MSBY position. Before decrementing the Y register, however, the higher-addressed MSBY is pushed onto the stack for later use. With several more Y register decrements, the two LSBYs are addressed and subtracted. The result of the subtraction is not saved, since we are only interested in the final status of the operation, not the numerical result.

         |           |                     |           |
         +-----------+                     +-----------+
ADDR     |   LSBY1   |            ADDR     |   LSBY2   |
         +-----------+                     +-----------+
ADDR + 1 |   MSBY1   |            ADDR + 1 |   MSBY2   |
         +-----------+                     +-----------+
ADDR + 2 |   LSBY2   |            ADDR + 2 |   LSBY1   |
         +-----------+                     +-----------+
ADDR + 3 |   MSBY2   |            ADDR + 3 |   MSBY1   |
         +-----------+                     +-----------+
         |           |                     |           |

    (A) Before Swap.                  (B) After Swap.

Figure 1: Swapping two 16-bit values in memory.

The most-significant bytes (MSBYs) are subtracted next, by retrieving the higher-addressed MSBY from the stack and subtracting the lower-addressed MSBY from it. With this subtraction, we can make the exchange/no-exchange decision based ont he state of the Carry flag. If Carry is set (no borrow occurred), the elements are in the correct order; if Carry is reset (a borrow occurred), the elements must be exchanged.

Figure 1 shows what the SWAP routine actually does, by presenting the “before” and “after” diagrams of the exchanged 16-bit elements. The higher-valued elements initially resides in symbolic addresses ADDR + 2 and ADDR + 3, and its bytes are designated as LSBY2 and MSBY2. The lower-valued elements initially resides in symbolic addressed ADDR and ADDR + 1, and its bytes are designated LSBY1 and MSBY1. The sequence of the SWAP routine will be more easily understood if you refer to Figure 1 while studying the instructions of the routine.

Due to the previous subtraction routine, the Y register index is pointing at MSBY1 when the SWAP routine is initiated. Taking advantage of this pointer, SWAP saves MSBY1 and the adjacent byte, LSBY1, on the stack. Recalling that information is retrieved from a stack in the opposite order from which it was entered on the stack, the MSBY1-then-LSBY1 push sequence implies which byte will be the next to be pushed onto the stack- it will be MSBY2. With these three bytes on the stack, the final byte LSBY2 is moved from ADDR + 2 (again, refer to Figure 1) to ADDR. A short loop (SLOOP) pulls bytes MSBY2, LSBY1, and MSBY1 off the stack and stores them in the locations following LSBY2. The SWAP routine ends by turning on the exchange flag in location $32. If Elements 1 and 2 were exchanged, a BEQ SORT16 instrucion branches to the top of the subroutine; otherwise, control jumps to NXTEL, for the next comparison.

base/bubble_sort_16-bit_elements.txt · Last modified: 2015-04-17 04:30 (external edit)