Sort Numbers in ascending order

As part of a project that I am working on, I have generated 6 random numbers. The query that I have is how to put these numbers into ascending order. I have used the principle of the bubble sort algorithm, and adapted it for picaxe. Currently, this is the code that I have, working on a 28X:

====CODE====
sort:
check1:
if b6>b7 then swap1
check2:
if b7>b8 then swap2
check3:
if b8>b9 then swap3
check4:
if b9>b10 then swap4
check5:
if b10>b11 then swap5
goto show_sort

swap1:
b12=b6
b6=b7
b7=b12
goto sort

swap2:
b12=b7
b7=b8
b8=b12
goto sort

swap3:
b12=b8
b8=b9
b9=b12
goto sort

swap4:
b12=b9
b9=10
b10=b12
goto sort

swap5:
b12=b10
b10=b11
b10=b12
goto sort

show_sort:

====END CODE====

I have not yet been able to test it, but I have posted it here for two reasons.
1) It appears rather long and messy for what it does, and wondered whether anybody would be able to tidy it up for me.
2)If this code does work, I believe that it could come in useful for other people, because a search on the forum revealed nothing of the sort.

Just to clarify a couple of points, variables b6-b11 are the numbers, and b12 is a temporary veriable.

Well, I think there are two key criteria: Speed and code space. It depends what's important. For instance you could have slow, but small, code that repeatedly scans a list of numbers (in RAM) picking off the largest and transferring to a new list (in RAM). The 'hole' in the first list is set to zero.

Something like this...
<code><pre><font size=2 face='Courier'>
Symbol SourceAddress = b0
Symbol DestAddress = b1
Symbol HighestAddress = b2
Symbol CurrentValue = b3
Symbol HighestAddress = b4

Symbol SourceStartAddress = 80
Symbol SourceEndAddress = 90
Symbol DestStartAddress = 192

Sort:
'Initialise
DestAddress = DestStartAddress
HighestValue =0

'Scan the Source list
For SourceAddress = SourceStartAddress To SourceEndAddress
Peek SourceAddress, CurrentValue

'Keep track of the highest value
If CurrentValue &gt; HighestValue Then
HighestAddress = SourceAddress
Endif
Next

'Transfer the highest value to the Destination list, and
'make the hole in the source list 0.
Poke HighestAddress,0
Poke DestAddress,HighestValue

Inc DestAddress

'If all values have been transferred from the source list
'then the highest value will be zero, in which case exit.
If HighestValue &gt;0 Then Sort
Return
</font></pre></code>

Only sensible to use this for small quantities of numbers.

Actually ....this probably isn't too good for your purpose. You've already got the number loaded in variables. Sorry !

Edited by - jeremy leach on 20/12/2006 10:28:15

The code only needs to be run once before the results are sent to be displayed on an LCD.
The code is repeated if a button is pressed.

Here's another go. This time making use of the fact that variables b0 etc are actually at RAM 50 onwards (I seem to remember). It's your bubble code basically written more efficiently...

<code><pre><font size=2 face='Courier'>


Symbol Var1 = b4
Symbol Var2 = b5
Symbol Address = b12

For Address = 56 to 60
'Load the temp variables
Peek Address,Var1
Inc Address
Peek Address,Var2

'Check and swap variables if necessary
If Var1 &gt; Var2 Then
Poke Address,Var1
Dec Address
Poke Address,Var2
Inc Address
Endif
Next
</font></pre></code>

But it uses b4 and b5 - I'm just assuming they are free !


Edited by - Jeremy Leach on 20/12/2006 10:44:58

Thankyou very much. Your second solution appears to be ideal.
Unfortunatly, I do not have any spare variables with my code at the moment, but I hope to tidy it up after your response.
Until now, I have been unaware that the code could be written in such a way.
I should be able to drasticly reduce the 700 line code as it is so far!

Actually, I think there's a bit missing. I think you need to run this a few times to ensure something bubbles from the bottom to top etc. So maybe need to enclose all this in a for next loop with a suitable count to cover the worse-case scenario.

<A href='http://en.wikipedia.org/wiki/Bubble_sort' Target=_Blank>External Web Link</a> See the random number example !!


Edited by - Jeremy Leach on 21/12/2006 13:20:08

Jeremy.

This is &quot;crude&quot;, but it works.
<code><pre><font size=2 face='Courier'>
'modified from forum 20 12 06

b6 = 100 : b7 = 90: b8 = 80 : b9 = 70 : b10 = 60 : b11 = 5

sertxd (cr,lf,&quot;***&quot;,#b6,&quot; &quot;,#b7,&quot; &quot;,#b8,&quot; &quot;,#b9,&quot; &quot;,#b10,&quot; &quot;,#b11,cr,lf)

Symbol Var1 = b4
Symbol Var2 = b5
Symbol Address = b12
'
for b3 = 1 to 5' Array n-1 *******
'
For Address = 56 to 60
'Load the temp variables
Peek Address,Var1
Inc Address
Peek Address,Var2

'Check and swap variables if necessary
If Var1 &gt; Var2 Then
Poke Address,Var1
Dec Address
Poke Address,Var2
'Inc Address '********
Endif
Next

sertxd (cr,lf,#b6,&quot; &quot;,#b7,&quot; &quot;,#b8,&quot; &quot;,#b9,&quot; &quot;,#b10,&quot; &quot;,#b11,cr)

next b3
</font></pre></code>

e.

Edited by - eclectic on 21/12/2006 13:30:26

I think you'll find that doesn't work for all number sequences ...<code><pre><font size=2 face='Courier'>b6 = 1 : b7 = 6: b8 = 2 : b9 = 5 : b10 = 3 : b11 = 4 </font></pre></code> The unbalanced Inc/Dec causes the FOR-NEXT loop Address to skip entries. This should fix it ...<code><pre><font size=2 face='Courier'>For Address = 56 to 60
Peek Address,Var1
Inc Address
Peek Address,Var2
Dec Address
If Var1 &gt; Var2 Then
Inc Address
Poke Address,Var1
Dec Address
Poke Address,Var2
Endif
Next </font></pre></code>

Edited by - hippy on 21/12/2006 13:54:30

Cheers Hippy.

Thanks for the inc / dec info.
e.

and how about this, using Peek Word, and assumes numbers to sort are less than 255 ... ;-)

<code><pre><font size=2 face='Courier'>
Symbol Vars = w3 'b4 and b5
Symbol Var1 = b4
Symbol Var2 = b5
Symbol Address = b12
Symbol RAM_Temp = 80

Do
Poke RAM_Temp , 255

For Address = 56 to 60
Peek Address,Word Vars
If Var1 &gt; Var2 Then
Poke RAM_Temp,Var2
Var2 = Var1
Peek RAM_Temp,Var1
Endif
Next

Peek RAM_Temp,Var1
Loop Until Var1 = 255
</font></pre></code>


Edited by - Jeremy Leach on 21/12/2006 15:15:41

Untested, but how about this to eliminate the outer loop by bubbling each element down as far as it will go?

<code><pre><font size=2 face='Courier'>
Symbol Var1 = b4
Symbol Var2 = b5
Symbol Address = b12

b6 = 4 : b7 = 6: b8 = 2 : b9 = 5 : b10 = 3 : b11 = 1
sertxd (cr,lf,&quot;***&quot;,#b6,&quot; &quot;,#b7,&quot; &quot;,#b8,&quot; &quot;,#b9,&quot; &quot;,#b10,&quot; &quot;,#b11,cr,lf)
Symbol Var1 = b4
Symbol Var2 = b5
Symbol Address = b12
'
For Address = 56 to 60
'Load the temp variables
Peek Address,Var1
Inc Address
Peek Address,Var2
'Check and swap variables if necessary
If Var1 &gt; Var2 Then
Poke Address,Var1
Dec Address
Poke Address,Var2
if Address &gt; 56
Dec Address ' bubble the comparison down
Endif
Endif
Dec Address
Next
sertxd (cr,lf,#b6,&quot; &quot;,#b7,&quot; &quot;,#b8,&quot; &quot;,#b9,&quot; &quot;,#b10,&quot; &quot;,#b11,cr)
</font></pre></code>

And, faster on average ...<code><pre><font size=2 face='Courier'>VarTop = 60
Do
Sorted = 1
For Address = 56 To VarTop
Peek Address,Var1
Inc Address
Peek Address,Var2
Dec Address
If Var1 &gt; Var2 Then
Inc Address
Poke Address,Var1
Dec Address
Poke Address,Var2
Sorted = 0
Endif
Next
Dec VarTop
Loop While Sorted = 0 And VarTop &gt;= 56 </font></pre></code>

Edited by - hippy on 21/12/2006 17:07:52

Excellent ....many ways to crack a nut <img src="wink.gif" width=15 height=15 align=middle>

Usually variable swaps (b0 &lt;--&gt; b1) are done as

tmp = b0
b0 = b1
b1 = tmp

but that needs a third variable - can be painful on a picaxe with only so few variables available. If you are short on variables then here is a neat little trick to swap two variables without using a third one, provided b0+b1 is no larger than 255:

b0 = x
b1 = y

' now swap
b0 = b0 + b1 ' variables hold (x+y) and y
b1 = b0 - b1 ' variables hold (x+y) and x
b0 = b0 - b1 ' variables hold y and x

Try it and see the magic at work

Wolfgang

PS: yes I know on the Picaxe I could use peek&amp;poke for holding tmp


Edited by - womai on 22/12/2006 00:39:47

That's a useful trick to remember, nice one !