# ### Site Tools

base:combination_sort_8-bit_elements

# Differences

This shows you the differences between two versions of the page.

 — base:combination_sort_8-bit_elements [2015-04-17 04:30] (current) 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.  By adding an additional zero page temp variable,    ; + ; 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)                                                ; + ;   DO                                                        ; + ;     gap = INT(gap / 1.3)                                    ; + ;     IF gap < 1 THEN gap = 1                                 ; + ;     switch = 0                                              ; + ;     FOR I = 1 TO size - gap                                 ; + ;       J = I + gap                                           ; + ;       IF A(I) > A(J) THEN                                   ; + ;         SWAP A(I), A(J)                                     ; + ;         switch = switch + 1                                 ; + ;       END IF                                                ; + ;     NEXT I                                                  ; + ;   LOOP UNTIL gap = 1 AND switch = 0                         ; + ;                                                             ; + ;  Daryl Rictor - May 2001                                    ; + ;                                                             ; + ;*************************************************************; + ; + ; + ; define variables + ; + array    =   \$30 + flag     =   \$32 + gap      =   \$33 + ; + ; + ; UPPERCASE opcodes are 6502 codes + ; lowercase opcodes are 65C02 codes + ; + + SORT8    lda (array)       ; FETCH ELEMENT COUNT + STA gap           ; save in gap + SORTLP   LSR gap           ; divide gap by ~1.3  (gap * 0.7692) + LDA gap           ; (not critical to be exact) + LSR A             ; this routine calculates it as: + CLC               ; + ADC gap           ;     gap = gap/2 + gap/4 + STA gap           ;     (gap * 0.7500) + CMP #\$00          ; + BNE CLFLAG        ; if gap = 0 then set it to 1 + INC gap           ; + CLFLAG   stz flag          ; TURN EXCHANGE FLAG OFF (= 0) + SEC               ; + lda (array)       ; get size + SBC gap           ; subract gap to reduce loop size + TAX               ; (loop counter & pointer to lower element) + NXTEL    CLC               ; calc pointer to upper element + TXA               ; + ADC gap           ; + TAY               ; y = x + gap + LDA (array),y     ; get upper element + PHA               ; save it for swap + phy               ; save y for swap + phx               ; transfer x reg to y reg + ply               ; get pointer to lower element + CMP (array),y     ; compare = upper - lower + BCS CLRSTK        ; if upper < lower, swap elements + LDA (array),y     ; get lower value + ply               ; get upper element pointer + STA (array),y     ; save lower value in upper element + phx               ; transfer x reg to y reg + ply               ; get lower element pointer + PLA               ; get upper value + STA (array),y     ; save upper vaule in lower element + LDA #\$FF          ; TURN EXCHANGE FLAG ON (= -1) + STA flag          ; + BNE CHKEND        ; skip over stack maintenance + CLRSTK   PLA               ; remove upper element & pointer from stack + PLA               ; + CHKEND   DEX               ; END OF LIST? + BNE NXTEL         ; NO. FETCH NEXT ELEMENT + LDA gap           ; + CMP #\$01          ; + BNE SORTLP        ; repeat loop unitl the gap size = 1 + BIT \$32           ; if gap = 1, IS EXCHANGE FLAG STILL OFF? + BMI SORTLP        ; NO. GO THROUGH LIST AGAIN + RTS               ; YES. LIST IS NOW ORDERED + ; + ; end SORT8 + ; + ;*************************************************************; + 