Bubble Sort In Basic - Sorting an indexed array

nick bernard

Hail Board,

i'm developing a little project that requires sorting and i just wanted to share what i have developed and exchange ideas about the algorithm and code in general. the tricky thing about my bubble sort is the way i indexed data in the scratch pad.

questions, comments, advise?

here is the code:

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
" Hey! Why is there silicone on my hemostats?"

Chris Savage

Nick,

·· Nice job!· And no sorting in the EEPROM!· LOL· I will have to check this out in more detail later, but I think it's the first sorting routine I have seen on the BASIC Stamp.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chris Savage
Parallax Tech Support
csavage@parallax.com

nick bernard

Chris said...
And no sorting in the EEPROM! LOL

har har har - Good memory dude.

there arent many applications for a bubble sort in the world of stamping. i suppose that's why it never came up. In any case i always liked the bubble sort because its a simple, easy-to-follow teaching tool for sorting even if its inefficient.

rox on

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
" Hey! Why is there silicone on my hemostats?"

allanlane5

And it takes very little code space. Since any array you'll want to sort HAS to be small, the inefficiency doesn't really hurt you.

Tracy Allen

Nice job, Nick! That kind of routine is also useful in statistics, to find things like the median or quartiles in a list of numbers. In digital filtering, a median filter is a powerful tool to reject readings with "pop" noise.

One suggestion, is that in some cases the the BUBBLE subroutine might be called when the array is already sorted, or when only one score has been added since the previous sort. In that case it there is no point in passing through the loop more than once or twice. I'd add a one bit flag variable that is set to TRUE before executing the inner loop, and set equal to FALSE if any swap takes place while passing through the inner loop. After the inner loop a test, IF noswaps THEN EXIT. Another small thing, if NOP is a constant, then NOP-2 is also a constant and a little program space and speed can be saved by also defining NOP2 CON NOP-2.

' Nick's code, slightly modified, untested!
'ax,cx are bytes for counting
'tmp_a,tmp_b,value,value2 are bytes for storage
'RANK and SCORE are constants that index locations in the scratch pad
' --- rank(0) holds index of highest score
' --- first pass through the inner loop brings the lowest score to rank(NOP-1)
'NOP is a constant for the number of players
'rank = 0
'score = 16
'NOP = 16
'swaps is a one bit flag
'the scratch pad 
'  0-15  rank of player1 -> player16
'  16-31 score of player 1 -> plater16
NOP2  CON NOP-2
BUBBLE:
  FOR ax = 0 TO NOP2                      'outer loop counts iterations of the inner loop
    noswaps=1   
    FOR cx = 0 TO NOP2 - ax             'inner loop counts through array and tests for swaps
      GET RANK + cx, tmp_a                 'gets the index of the cx'th ranked player
      GET RANK + cx + 1, tmp_b           'gets the index of the next ranked player
      GET SCORE + tmp_a, value          'gets the score the the cx'th ranked player
      GET SCORE + tmp_b, value2        'gets the score of the next player
      IF value < value2 THEN                'if the cx'th player's score is less than the next player's score
        PUT RANK + cx, tmp_b               'swap the index in the ranking 
        PUT RANK + cx + 1, tmp_a
    noswaps=0                           ' -- okay, there was at least one swap during inner loop
      ENDIF                                         'otherwise leave them alone
    NEXT
      IF noswaps THEN EXIT
 NEXT
  RETURN

I have a median routine at www.emesystems.com/BS2math5.htm, but I think your ranked bubble sort would be a better way to go about that. I came at it in a different way, iteratively extracting the minimum and maximum from a list.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

nick bernard

sure - the outer loop should be

do while (noswaps)
nexted swaping routine
loop

this would minimize the number of iterations of the swapping routine

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
" Hey! Why is there silicone on my hemostats?"