comb sort

[bogax]

I've been doodling.

Here's a first whack at a comb sort.

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

Edit: clarified (I hope) the comments some

[8BIT]

This looks similar to the combo sort I wrote several years back.
It's in the Source Code repository here

http://www.6502.org/source/sorting/combo.htm

Cheers!

Daryl

[ElEctric_EyE]

...

[bogax]

8BIT wrote:

This looks similar to the combo sort I wrote several years back.
It's in the Source Code repository here

http://www.6502.org/source/sorting/combo.htm

Cheers!

Daryl

Mine's bigger ... er ... faster

[8BIT]

Yeah, I used the stack to do the swap, which eats up cycles.

Your swap code is much more efficient.

Wouldn't it have been great if the 65xx family had included a SWAP instruction? Also, a swap nibble instruction would have been nice too.

Daryl

[bogax]

Here's a shorter version
Less code, but more cycles

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

[bogax]

8BIT wrote:

Yeah, I used the stack to do the swap, which eats up cycles.

Your swap code is much more efficient.

Wouldn't it have been great if the 65xx family had included a SWAP instruction? Also, a swap nibble instruction would have been nice too.

Daryl

Swapping bytes might be nice.

As far as nibbles I think what I'd really like is being able to load
a register with just either the top nibble or the bottom nibble

eg

A = AB
load Y so you could have either Y = 0A or Y = 0B

[RichTW]

"Swap nibble" is #1 on my list of instructions I wish they'd implemented - it would've been a real cycle saver on so many occasions. Are there any 8-bit architectures which have it?

[8BIT]

The Atmel AVR's have it. That's were I've used it.

[BitWise]

PICs have it too.

I seem to remember the Z80 having a complex nybble rotate instruction involving A and (HL) -- RLD & RRD

[RichTW]

Crikey, you're right!

http://z80-heaven.wikidot.com/instructions-set:rld says:

Quote:

Performs a 4-bit leftward rotation of the 12-bit number whose 4 most signigifcant bits are the 4 least significant bits of A, and its 8 least significant bits are in (HL).

How obscure! I even wrote a Z80 emulation many years ago, and don't remember those instructions. The Z80 was bloated full of curiosities like that.

[bogax]

8BIT wrote:

This looks similar to the combo sort I wrote several years back.
It's in the Source Code repository here

http://www.6502.org/source/sorting/combo.htm

Cheers!

Daryl

After studying on your code some, it occurs to me that I can
pretty much just drop sorting the last element ie the first
location in the page.

So here's a version of mine that's almost as fast as the fast one
and almost as short as the short one.
But it only does 255 elements
(and I moved the number of elements to the first location
in the page similar to yours)

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

[JimBoyd]

8BIT wrote:

This looks similar to the combo sort I wrote several years back.
It's in the Source Code repository here

http://www.6502.org/source/sorting/combo.htm

Cheers!

Daryl

Which looks similar to the Combsort presented by Stephen Lacey and Richard Box in the April 1991 issue of Byte magazine. The article starts on page 315.

[8BIT]

JimBoyd wrote:

Which looks similar to the Combsort presented by Stephen Lacey and Richard Box in the April 1991 issue of Byte magazine. The article starts on page 315.

Yes, I mention that I had seen it somewhere but did not have the reference. Back then, i kept a folder of cool routines but lost the folder in a move.

Thanks for pointing it out. I'll see if I can get it added to the repository copy.

Daryl