6502.org

Code: Select all

 ; comb sort list of (up to) 256 8 bit elements.
 ; list must be page aligned
 ; top =   location containing the location in the
 ;         list page of the last list element
 ;         = number of list elements - 1 (list is
 ;         zero based, page aligned) 
 ;         ie if there's 3 elements in the list
 ;         top contains 2
 ; upper = lo byte of the zp pointer of upper list
 ;         element to compare. upper contains gap
 ; list =  address of first element of list. Must be
 ;         page aligned 

 ; Upper is set to the gap and Y is set to top - gap
 ; so initially, (upper) + Y = top and
 ; list + Y = top - gap
 ; Then the inner loop decrements Y to zero, comparing,
 ; and swapping as needed. The V flag is set at the begining
 ; of the inner loop and each time a swap is performed
 ; the V flag is cleared
 ; The outer loop decreases the gap by a factor of 1.33
 ; untill the gap is one and then exits when an inner loop
 ; does no swaps.
 ; In order to avoid an explicit cpy in the inner loop,
 ; we exit  the inner loop when Y = 0 which still leaves
 ; a compare for Y = 0 to do.
 ; So seperate code is provided for that.
 ; Two special cases must be provided for.    
 ; If there's only one element we just skip it all
 ; If there's only two elements we jump directly to the
 ; Y = 0 code and provide a special exit from the sort
 ; routine for the case of two elements. Fortunately the
 ; special case handling can be mostly out side the main
 ; loop(s) and doesn't add much in the way of cycles used

 ;intialize zp
 lda #>list
 sta upper+1

SORT

 ; first, corner case kludges
 lda top
 beq RETURN        ; don't try and sort one element
 sta upper
 cmp #$01          ; if there's only two elements
 bne NEXT_GAP      ; the first compare is the last
 ldy #$00          ; but Y still needs initializing
 beq LAST_COMPARE


 ; shrink factor 1.33
 ; multiply gap by reciprocal = .75
NEXT_GAP
 lsr               ; .5 x gap
 adc upper         ; + gap = 1.5 x gap
 ror               ; (1.5 x gap)/2 = .75 gap
 sta upper         ; no clc and gap will never = 0
                   ; so minimum result = 1              
NEXT_GAP_1
 eor #$FF          ; negate gap
 sec
 adc top           ; add to top to get
 tay               ; top - gap = index
 lda #$7F
 adc #$7F          ; clear the swapped flag ie set overflow 
 bvs LOOP

SWAP
 ldx list,y        ; get the lower element into X, out of the way
 sta list,y        ; copy the the upper element in A to the lower
 txa               ; position and the lower element in X
 sta (upper),y     ; into the upper position
 clv               ; set the swapped flag
 dey               ; screw it we'll just waste a couple bytes
 beq LAST_COMPARE  ; to decrement and test the index here and save
                   ; branching time. I love spaghetti
LOOP
 ; compare
 lda (upper),y     ; get the upper element to compare into A
 cmp list,y        ; compare to the lower element 
 bcc SWAP          ; if the lower element is > then go swap 'em  
 dey               ; damn, decrement and test again already!?
 bne LOOP

LAST_COMPARE
 ; seperate compare and swap for Y = 0
 lda (upper),y     ; we tested/fell through on index = 0 for speed 
 cmp list,y        ; so we still need to do compare for index = 0
 bcs SKIP  

 ; swap
 ldx list,y        ; and swap if that seems necessary
 sta list,y
 txa
 sta (upper),y
 clv               ; set the swapped flag ie clv

SKIP
 lda upper         ; get the current gap
 cmp #$01          ; and see if it's = 1
 bne NEXT_GAP      ; if not go calculate the next gap
 cmp top           ; corner case kludge
 bcs RETURN        ; if top <= 1 no more sorting can be needed
 bvc NEXT_GAP_1    ; done swapping? if not, no need to calculate
                   ; gap since gap = 1
RETURN
 rts

Code: Select all

 ; comb sort list of (up to) 256 8 bit elements.
 ; list must be page aligned
 ; top =   location containing the location in the
 ;         list page of the last list element
 ;         = number of list elements - 1 (list is
 ;         zero based, page aligned) 
 ;         ie if there's 3 elements in the list
 ;         top contains 2
 ; upper = lo byte of the zp pointer of upper list
 ;         element to compare. upper contains gap
 ; list =  address of first element of list. Must be
 ;         page aligned 

 ; Upper is set to the gap and Y is set to top - gap
 ; so initially, (upper) + Y = top and
 ; list + Y = top - gap
 ; Then the inner loop decrements Y to zero, comparing,
 ; and swapping as needed. The V flag is set at the begining
 ; of the inner loop and each time a swap is performed
 ; the V flag is cleared
 ; The outer loop decreases the gap by a factor of 1.33
 ; untill the gap is one and then exits when an inner loop
 ; does no swaps.
 ; If there's only one element we just skip it all

COMB_SORT

 ; first, a corner case kludge
 lda top
 beq RETURN        ; don't try and sort one element
 sta upper

 ; shrink factor 1.33
 ; multiply gap by reciprocal = .75
NEXT_GAP
 lsr               ; .5 x gap 
 adc upper         ; + gap = 1.5 x gap 
 ror               ; (1.5 x gap)/2 = .75 gap 
 sta upper         ; no clc and gap will never = 0 
                   ; so minimum result = 1              
 
NEXT_GAP_1
 eor #$FF          ; negate gap
 sec
 adc top           ; add to top to get
 tay               ; top - gap = index
 lda #$7F
 adc #$7F          ; clear swapped flag ie set overflow 
 bvs COMPARE

SWAP
 ldx list,y        ; get the lower element into X, out of the way 
 sta list,y        ; copy the the upper element in A to the lower 
 txa               ; position and the lower element in X 
 sta (upper),y     ; into the upper position 
 clv               ; set the swapped flag 

 ; last element test here adds bytes but saves branching time
 ; I love spaghetti
 cpy #$00          ; was that the last element?
 beq OUTER         ; if so, go do the next gap

COMPARE_LOOP
 dey
COMPARE
 lda (upper),y     ; get the upper element to compare into A
 cmp list,y        ; compare it to the lower element 
 bcc SWAP          ; if the lower element is > then go swap 'em  
 cpy #$00          ; was that the last element?
 bne COMPARE_LOOP  ; if not, go do another

OUTER
 lda upper         ; get the current gap
 cmp #$01          ; and see if it's = 1
 bne NEXT_GAP      ; if not go calculate the next gap
 bvc NEXT_GAP_1    ; done swapping? if not, no need to
                   ; calculate gap since gap = 1
RETURN
 rts

Code: Select all

 ; comb sort list of (up to) 255 8 bit elements.

 ; list =  first (ie zero) address of the page containing
 ;         the list. the contents of list, (list),
 ;         = location in the page of the last list element
 ;         = number of list elements
 ;    
 ; upper = lo byte of the zp pointer of upper list
 ;         element to compare. upper contains gap

 ; the first element is in the xx01 location in the list page
 ; ie the second location in the page
 ; upper is set to the gap.
 ; Y is set to (list) - gap
 ; so initially, (upper) + Y  points to the last element
 ; list + Y points to the element [gap] elements below the first
 ; Then the inner loop decrements Y to zero, comparing,
 ; and swapping as needed. The V flag is set at the begining
 ; of the inner loop and each time a swap is performed
 ; the V flag is cleared
 ; The outer loop decreases the gap by a factor of 1.33
 ; untill the gap is one and then exits when an inner loop
 ; does no swaps.
 ; If there's only one element we just skip it all

COMB_SORT 
 ;intialize zp 
 lda #>list 
 sta upper+1 

 ; first, a corner case kludge 
 lda list 
 cmp #$01
 beq RETURN        ; don't try and sort one element 
 sta upper 

 ; shrink factor 1.33 
 ; multiply gap by reciprocal = .75 
NEXT_GAP 
 lsr               ; .5 x gap 
 adc upper         ; + gap = 1.5 x gap 
 ror               ; (1.5 x gap)/2 = .75 gap 
 sta upper         ; no clc and gap will never = 0 
                   ; so minimum result = 1              
NEXT_GAP_1 
 eor #$FF          ; negate gap 
 sec 
 adc list          ; add to (list), ie the location of last 
 tay               ; the element to get (list) - gap = index 
 lda #$7F 
 adc #$7F          ; clear the swapped flag ie set overflow 
 bvs LOOP 

SWAP 
 ldx list,y        ; get the lower element into X, out of the way 
 sta list,y        ; copy the the upper element in A to the lower 
 txa               ; position and the lower element in X 
 sta (upper),y     ; into the upper position 
 clv               ; set the swapped flag 
 ; screw it we'll decrement and test the index here 
 ; and save branching time. I love spaghetti 
 dey               ; if that's the last element 
 beq OUTER_LOOP    ; go do the next gap   

LOOP 
 ; compare 
 lda (upper),y     ; get the upper element to compare into A 
 cmp list,y        ; compare to the lower element 
 bcc SWAP          ; if the lower element is > then go swap 'em  
 dey               ; damn, decrement and test again already!? 
 bne LOOP          ; if that wasn't the last element go do
                   ; another  

OUTER_LOOP 
 lda upper         ; get the current gap 
 cmp #$01          ; and see if it's = 1 
 bne NEXT_GAP      ; if not go calculate the next gap 
 bvc NEXT_GAP_1    ; done swapping? if not, no need to calculate 
                   ; gap since gap = 1 
RETURN 
 rts