base:combination_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:combination_sort_8-bit_elements [2015-04-17 04:30] (current) – created - external edit 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== Combination Sort ====== | ||
+ | by Daryl Rictor | ||
+ | This is a sort routine called a Combination Sort, which is a modified bubble sort (iterative) that takes much less time to complete. | ||
+ | |||
+ | As an example, using a 255 element array, the standard bubble sort routine found elsewhere in the repository took on average about 2 seconds to complete on my computer. My routine took about 2/10ths of a second to sort the same data. I used three different random patterns and used my TOD timer to perform the time measurements. | ||
+ | < | ||
+ | ; | ||
+ | ; ; | ||
+ | ; Combination Sort - An improvement on the Bubble Sort ; | ||
+ | ; ; | ||
+ | ; | ||
+ | ; ; | ||
+ | ; This idea was presented as a BASIC program in a magazine | ||
+ | ; article about 12 years ago. I could not find the orginal | ||
+ | ; article and I do not know who the author was. I am ; | ||
+ | ; including the BASIC routine that I had used in some of my ; | ||
+ | ; BASIC programs. | ||
+ | ; ; | ||
+ | ; As I recall, this sort routine cuts the processing time by ; | ||
+ | ; reducing the size of the array into smaller chuncks, and ; | ||
+ | ; moving each elelment more than one position at a time, thus ; | ||
+ | ; reducing the total number of cycles through the loop. I ; | ||
+ | ; have not seen a faster, non-recursive sort routine. | ||
+ | ; ; | ||
+ | ; I have taken the BASIC routine and converted it to 65C02 ; | ||
+ | ; assembly code. I am using the added opcodes PHX, PHY, ; | ||
+ | ; PLX, PLY, LDA (zp) & STZ zp to decrease size and increase | ||
+ | ; speed. | ||
+ | ; you can use the basic 6502 opcodes to perform this sort. ; | ||
+ | ; ; | ||
+ | ; Here's my copy of the BASIC Routine: | ||
+ | ; ; | ||
+ | ; SUB COMBINATION (A()) ; | ||
+ | ; size = A(0) ; | ||
+ | ; gap = A(0) ; | ||
+ | ; | ||
+ | ; gap = INT(gap / 1.3) ; | ||
+ | ; IF gap < 1 THEN gap = 1 ; | ||
+ | ; | ||
+ | ; FOR I = 1 TO size - gap ; | ||
+ | ; J = I + gap ; | ||
+ | ; IF A(I) > A(J) THEN ; | ||
+ | ; SWAP A(I), A(J) ; | ||
+ | ; | ||
+ | ; END IF ; | ||
+ | ; NEXT I ; | ||
+ | ; LOOP UNTIL gap = 1 AND switch = 0 ; | ||
+ | ; ; | ||
+ | ; Daryl Rictor - May 2001 ; | ||
+ | ; ; | ||
+ | ; | ||
+ | ; | ||
+ | ; | ||
+ | ; define variables | ||
+ | ; | ||
+ | array = $30 | ||
+ | flag | ||
+ | gap = $33 | ||
+ | ; | ||
+ | ; | ||
+ | ; UPPERCASE opcodes are 6502 codes | ||
+ | ; lowercase opcodes are 65C02 codes | ||
+ | ; | ||
+ | |||
+ | SORT8 lda (array) | ||
+ | STA gap ; save in gap | ||
+ | SORTLP | ||
+ | LDA gap ; (not critical to be exact) | ||
+ | LSR A ; this routine calculates it as: | ||
+ | | ||
+ | ADC gap ; | ||
+ | STA gap ; | ||
+ | CMP #$00 ; | ||
+ | BNE CLFLAG | ||
+ | INC gap ; | ||
+ | CLFLAG | ||
+ | | ||
+ | lda (array) | ||
+ | SBC gap ; subract gap to reduce loop size | ||
+ | | ||
+ | NXTEL CLC ; calc pointer to upper element | ||
+ | | ||
+ | ADC gap ; | ||
+ | | ||
+ | LDA (array), | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | CMP (array), | ||
+ | BCS CLRSTK | ||
+ | LDA (array), | ||
+ | | ||
+ | STA (array), | ||
+ | | ||
+ | | ||
+ | | ||
+ | STA (array), | ||
+ | LDA #$FF ; TURN EXCHANGE FLAG ON (= -1) | ||
+ | STA flag ; | ||
+ | BNE CHKEND | ||
+ | CLRSTK | ||
+ | | ||
+ | CHKEND | ||
+ | BNE NXTEL ; NO. FETCH NEXT ELEMENT | ||
+ | LDA gap ; | ||
+ | CMP #$01 ; | ||
+ | BNE SORTLP | ||
+ | BIT $32 ; if gap = 1, IS EXCHANGE FLAG STILL OFF? | ||
+ | BMI SORTLP | ||
+ | | ||
+ | ; | ||
+ | ; end SORT8 | ||
+ | ; | ||
+ | ; | ||
+ | </ |
base/combination_sort_8-bit_elements.txt · Last modified: 2015-04-17 04:30 by 127.0.0.1