A Simple Sort

A

AndyGadget

Senior Member
Below is a simple snippet to sort three variables into ascending order. It's a bubble sort which works fine, but is there a more compact way to do this? It's for an 08m so can't use SWAP, which is only available on X2 and M2 chips.

Code: 
#picaxe 08m

symbol Tmp	= b0 
symbol D1	= b6
symbol D2	= b7
symbol D3	= b8

do
	readadc 1,d1
	readadc 2,d2
	readadc 4,d3

	if d1 > d2 then
		tmp = d1
		d1 = d2
		d2 = tmp
	endif

	if d2 > d3 then
		tmp = d2
		d2 = d3
		d3 = tmp
	endif

	if d1 > d2 then
		tmp = d1
		d1 = d2
		d2 = tmp
	endif

	wait 2
loop
 
A

AndyGadget

Senior Member
Doing the whole loop twice cuts the size down by 5 bytes with an increase in execution time.

Code: 
#picaxe 08m

symbol tmp   = b0 
symbol tmp2 = b1
symbol D1    = b6
symbol D2	  = b7
symbol D3	  = b8

do
	readadc 1,d1
	readadc 2,d2
	readadc 4,d3

	for tmp2 = 0 to 1

		if d1 > d2 then
			tmp = d1
			d1 = d2
			d2 = tmp
		endif

		if d2 > d3 then
			tmp = d2
			d2 = d3
			d3 = tmp
		endif

	next tmp2	

	wait 2
loop
 
W

westaust55

Moderator
Your post uses three values.

Is that a fixed or are added variable a possibility?
Other forms of data sort can come in to their own when the number of values is in the 8 to 20 bytes range.

Are number of variables required a problem? Could consider using SFR RAM locations other than "standard variables" but that may be at the expense of program size.

Some commands on the "bigger"/newer chips do not significantly save space. Think from memory that "SWAP" is in that category using a "system" variable and performing several steps which while looking simpler with a single command in the BASIC text actiually does not save as much program space as might be imagined.
 
A

AndyGadget

Senior Member
I'm aware of the formal search types for 'n' values but this is just a simple application which uses only the three variables which I want sorted. They're actually going to be delays where I want shortest first, but entering the sort they may be in any order.
The READADC commands are just there for simulation testing - it's the sort technique I'm interested in.

You're right about SWAP not being smaller. If I call the chip a 20x2 the SWAP version is exactly the same size as using a temporary variable. If I call the chip an 18m2 it's 10 bytes bigger! (C'mon Rev-ed - Don't get lazy ;¬)

Edit: The sort is 28 bytes at the moment which is fine as I'm not (yet) pushed for space.
The question was really aimed at whether I'd missed a more subtle way of doing this.
 
Last edited:
G

geoff07

Senior Member
If there are only a few values, perhaps for incoming events that have to queue until their time, why not store them in sorted order, perhaps a linked list in some form. Then no need to sort at all, just a bit more code to add them to the right place in the list.
 
W

westaust55

Moderator
Likely there is no more program space efficient means for a small number of values. But . . . hippy may find a way where others cannot.

I tried with using PEEK and POKE commands since we know where the variables are stored.

My result was mid way between you own two code snippets

Code: 
#picaxe 08m

symbol counter  = b0 
symbol index    = b1
symbol temp1    = b2
symbol temp2    = b3

symbol d1    = b6
symbol d2    = b7
symbol d3    = b8
symbol d4    = b9
symbol d5    = b10

SYMBOL startptr = 56 ; PIC SRF RAM location for  d1 = variable b6 (starts with b0 at location 50)
SYMBOL totalloops = 4  ; 3 values ==> 4 loops, 4 values ==> 10 loops, 5 values ==> 20 loops

do
	readadc 1,d1
	readadc 2,d2
	readadc 4,d3

;d1 = 9
;d2 = 7
;d3 = 5
;d4 = 3
;d5 = 1

	index = startptr
	for counter = 1 to totalloops ; note counter starts at 1 
		PEEK index,temp1 
		INC index
		PEEK index,temp2
		IF temp1 > temp2 THEN
			POKE index,temp1
			DEC index
			POKE index,temp2 
			index = startptr
		ENDIF
	next counter	
	wait 2
loop

For you code segment:
Code: 
	for tmp2 = 0 to 1
		if d1 > d2 then
			tmp = d1
			d1 = d2
			d2 = tmp
		endif
		if d2 > d3 then
			tmp = d2
			d2 = d3
			d3 = tmp
		endif
	next tmp2
I register 32 bytes of program space required


For the example I have given the sort code is 34 bytes - so slightly longer.

The advantage of my code is that it remains the same sizr for more values, you just change the number of times through the loop.
This would work for any non X1/X2/M2 PICAXE so you could use variables b6 to b13 = 8 values in total.
 
Last edited:
You must log in or register to reply here.
Top