base:bubble_sort_16-bit_elements
no way to compare when less than two revisions
Differences
This shows you the differences between two versions of the page.
— | base:bubble_sort_16-bit_elements [2015-04-17 04:30] (current) – created - external edit 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== 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 [[bubble_sort_8-bit_elements|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, | ||
+ | < | ||
+ | ;THIS SUBROUTINE ARRANGES THE 16-BIT ELEMENTS OF A LIST IN | ||
+ | ;ASCENDING ORDER. | ||
+ | ;$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 | ||
+ | STY $32 | ||
+ | LDA ($30), | ||
+ | | ||
+ | NXTEL LDA ($30), | ||
+ | | ||
+ | DEY | ||
+ | LDA ($30), | ||
+ | SEC | ||
+ | DEY | ||
+ | DEY | ||
+ | SBC ($30), | ||
+ | PLA | ||
+ | INY | ||
+ | SBC ($30), | ||
+ | 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 | ||
+ | RTS | ||
+ | |||
+ | ;THIS ROUTINE BELOW EXCHANGES TWO 16-BIT ELEMENTS IN MEMORY | ||
+ | |||
+ | SWAP LDA ($30), | ||
+ | PHA | ||
+ | DEY | ||
+ | LDA ($30), | ||
+ | PHA | ||
+ | INY | ||
+ | INY | ||
+ | INY | ||
+ | LDA ($30), | ||
+ | PHA | ||
+ | DEY | ||
+ | LDA ($30), | ||
+ | DEY | ||
+ | DEY | ||
+ | STA ($30), | ||
+ | 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 | ||
+ | | ||
+ | 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, | ||
+ | |||
+ | 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 " | ||
+ | |||
+ | Operations on multiple-precision elements typically require a lot of pointer manipulation, | ||
+ | < | ||
+ | | ||
+ | | ||
+ | ADDR | ||
+ | | ||
+ | ADDR + 1 | | ||
+ | | ||
+ | ADDR + 2 | | ||
+ | | ||
+ | ADDR + 3 | | ||
+ | | ||
+ | | ||
+ | |||
+ | (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, | ||
+ | |||
+ | Figure 1 shows what the SWAP routine actually does, by presenting the " | ||
+ | |||
+ | 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 by 127.0.0.1