base:bubble_sort_8-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_8-bit_elements [2015-04-17 04:30] (current) – created - external edit 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== Bubble Sort (for 8-Bit Elements) ====== | ||
+ | from 6502 Software Design | ||
+ | ====== A Simple Sorting Technique ====== | ||
+ | Although unordered data are perfectly acceptable for many applications, | ||
+ | |||
+ | Just as bubble rise upward into the sky, list elements rise upward in memory during a bubble sort. (Data can be sorted in an increasing or decreasing order; we will discuss only increasing order). During a bubble sort, elements of a list are accessed sequentially, | ||
+ | |||
+ | If the bubble-sort algorithm is used, the microcomputer usually requires several passes to sort a list, as can be seen by the following example. Consider a 5-element list that is initially arranged in the following order. | ||
+ | < | ||
+ | 05 03 04 01 02 | ||
+ | </ | ||
+ | After one pass through the list, the elements will be in the following order: | ||
+ | < | ||
+ | 03 04 01 02 05 | ||
+ | </ | ||
+ | Element 05, the largest element of the list, has " | ||
+ | < | ||
+ | 03 01 02 04 05 | ||
+ | </ | ||
+ | Element 04 is bubbled up the list to a position that is just before Element 05. The result of the final pass is: | ||
+ | < | ||
+ | 01 02 03 04 05 | ||
+ | </ | ||
+ | The example not only demonstrates how the bubble sort algorithm operates, but it also gives an indication of what type of performance you can expect from it. Note that three passes were required to sort a partialy ordered, 5-element list. If the list were totally ordered at the outset, it would still take one pass through the algorithm to deduce this fact. Conversely, if the list were initially arranged in descending order (the worst case), the bubble-sort algorithm woul require 5 passes to order the list, 4 passes to sort, and 1 additional pass to detect that no additional elements need to be exchanged. From this observation, | ||
+ | |||
+ | What constitutes a " | ||
+ | |||
+ | ====== Sorting Lists Having 8-bit Elements ====== | ||
+ | |||
+ | The subroutine (SORT8) sorts unordered lists that are comprised of 8-bit elements. As in the previous examples in this chapter, the starting addres is contained in locations $30 (low-address byte) and $31 (high-address byte). The length of the list is contained in the first byte of the list. Since a byte is 8 bits wide, the list can contain up to 255 elements. | ||
+ | < | ||
+ | ;THIS SUBROUTINE ARRANGES THE 8-BIT ELEMENTS OF A LIST IN ASCENDING | ||
+ | ; | ||
+ | ;$31. THE LENGTH OF THE LIST IS IN THE FIRST BYTE OF THE LIST. LOCATION | ||
+ | ;$32 IS USED TO HOLD AN EXCHANGE FLAG. | ||
+ | |||
+ | SORT8 LDY #$00 ;TURN EXCHANGE FLAG OFF (= 0) | ||
+ | STY $32 | ||
+ | LDA ($30), | ||
+ | | ||
+ | | ||
+ | | ||
+ | NXTEL LDA ($30), | ||
+ | INY | ||
+ | CMP ($30), | ||
+ | BCC CHKEND | ||
+ | BEQ CHKEND | ||
+ | ;YES. EXCHANGE ELEMENTS IN MEMORY | ||
+ | | ||
+ | LDA ($30), | ||
+ | | ||
+ | STA ($30), | ||
+ | | ||
+ | | ||
+ | STA ($30), | ||
+ | LDA #$FF ;TURN EXCHANGE FLAG ON (= -1) | ||
+ | STA $32 | ||
+ | CHKEND | ||
+ | BNE NXTEL ;NO. FETCH NEXT ELEMENT | ||
+ | BIT $32 ;YES. EXCHANGE FLAG STILL OFF? | ||
+ | BMI SORT8 ;NO. GO THROUGH LIST AGAIN | ||
+ | | ||
+ | </ | ||
+ | Subroutine SORT8 begins by initializing an exchange flag. The exchange flag is an indicator in memory location $32 that can be interrogated upon completion of a sorting pass to find out whether any elements were exchanged during that pass (flag=-1) or if the pass was exected with no exchanges (flag=0). The latter case indicates that the list is completely ordered and needs no further sorting. | ||
+ | |||
+ | After loading the element count into the X register, the 6502 microprocessor enters an element compare loop at NXTEL. As each element is fetched, it is compared to the next element in the list, with CMP ($30),Y. If this pair of elements are of equal value, or are in ascending (sorted) order, the subroutine then branches to CHKEND, to see if the element count in the X register has been decremented to zero (the end-of-list condition). Otherwise, the elements are exchanged (if the element pair is in the wrong order). The stack is used to save the lower-addressed element while the higher-addressed element is being relocated in memory. A zero page memory location could have been used to save the element, but it was observed that PHA and PLA both execute in one less cycle than their LDA and STA counterparts. Upon completion of an exchange operation, the exchange flag is turned on, by loading it with -1. | ||
+ | |||
+ | Following the exchange, the element count is decremented with a DEX instruction (label CHKEND) and the subsequent BNE BXTEL instruction branches to NXTEL if the pass has not yet been completed. When the pass is completed, BIT $32 checkes whether the exhange is still off (Bit 7=0), or has been turned on (Bit 7=1) by an exchange operation during the pass. If an exchange occurred, the subroutine is reinitiated at ORDER8, otherwise RTS causes a return, with a now ordered list. | ||
+ | |||
+ | See also the [[bubble_sort_16-bit_elements|16-bit Bubble Sort routine]]. |
base/bubble_sort_8-bit_elements.txt · Last modified: 2015-04-17 04:30 by 127.0.0.1