Bubble sort

Bubble sort is probably the simplest sorting algorithm and does not require additional storage place which makes it an “in place sorting algorithm”.

This feature is particularly useful for devices with limited RAM storage as are AVR microprocessors. The bubble sort works by iterating down an array to be sorted from the first element to the last, comparing each pair of elements and swapping their positions if necessary. Thus, smaller elements will "bubble" to the front, (or bigger elements will be "bubbled" to the back, depending on implementation) and hence the name. Bubble sort is stable, as two equal elements will never be swapped. Let us see an example of sorting an array to make the idea of bubble sort clearer.

{25, 0, 13, -5, 16, 0, 1, 14}

Here i will slightly modify the algorithm so that iteration over the array goes until the last swap index is reached thus the sorting speed is improved. The code "remebers" the last index of the array where an element swap occured and the next iteration stops when this array index is reached. Instead of always scanning to the last array index each iteration scans through ever dicreasing element number thus improving the speed.

First iteration.

Starting comparing from first element upward,swapping the adjacent elements if smaller index element is bigger.

Keep on iterating....

...until the end of the array is reached.

Second iteration.

Third iteration...

Keep on iterating as long as a swap between adjacent elements is present.

Avr assembler implementation is prepared for 8  and 16 bits signed and unsigned numbers.

Signed 1 byte Bubble sort.


/**********************************************************************

8 bit bubble sort for signed/unsigned numbers up to 256 values

@AUTHOR:Sergey Iliev/Sofia

***********************************************************************/

#define BUFFER_SIZE 255

#define INDEX_LIMIT BUFFER_SIZE-1   ;zero based index

.dseg

buffer:  .byte BUFFER_SIZE

.cseg


/*************************8 bit Signed Bubble Sort*****************************************

;Sort signed bytes between -128 and 127

*@INPUT:RAM buffer with signed bytes to sort

*@USAGE:Z - pointer to buffer beginning

       right - marks the last index 2 adjacent numbers have been exchanged

       cnt - index

       axl,bxl - bytes to compare

       k - help variable

*@OUTPUT:RAM buffer sorted out!

*****************************************************************************************/

Signed8bitBubbleSort:

ldi    right,INDEX_LIMIT    ;size of array - 1

sort:

clr k

ldi    ZL,low(BUFFER)

ldi    ZH,high(BUFFER)


clr cnt         

i_loop:

ld axl,Z+

ld bxl,Z

cp bxl,axl      ;small trick to eliminate equal consequitive number index marking

brge i_loop1   ;signed

st -Z,bxl

adiw Z,1

st Z,axl

mov k,cnt

i_loop1:

inc cnt

cp cnt,right

brne i_loop

 

mov right,k

tst right

brne sort

ret

Unsigned 1 byte Bubble sort.

/*************************8 bit Unsigned Bubble Sort*****************************************

;Sort unsigned bytes between 0 and 255

*@INPUT:RAM buffer with unsigned bytes to sort

*@USAGE:Z - pointer to buffer beginning

       right - marks the last index 2 adjacent numbers have been exchanged

       cnt - index

       axl,bxl - bytes to compare

       k - help variable

*@OUTPUT:RAM buffer sorted out!

*****************************************************************************************/

Unsigned8bitBubbleSort:

ldi    right,INDEX_LIMIT    ;size of array - 1

usort:

clr k

ldi    ZL,low(BUFFER)

ldi    ZH,high(BUFFER)


clr cnt

ui_loop:

ld axl,Z+

ld bxl,Z

cp bxl,axl      ;small trick to eliminate equal consequitive number index marking {2,1,1,1,23....}

brsh ui_loop1  ;unsigned

st -Z,bxl

adiw Z,1

st Z,axl

mov k,cnt

ui_loop1:

inc cnt

cp cnt,right

brne ui_loop

 

mov right,k

tst right

brne usort

ret

Signed 2 byte Bubble sort.


/**********************************************************************

16 bit bubble sort for signed/unsigned numbers up to 2^16 numbers

@AUTHOR:Sergey Iliev/Sofia

***********************************************************************/


#define BUFFER_SIZE16 521

#define INDEX_LIMIT16 BUFFER_SIZE16-1   ;zero based index

.dseg

buffer16:  .byte BUFFER_SIZE16*2

.cseg



.MACRO CP16

    cp    @0,@2    ;Compare low byte

   cpc    @1,@3    ;Compare high byte with carry from

                                                   ;previous operation

.ENDMACRO

.MACRO ADDI16

  subi @0,low(-@2)

  sbci @1,high(-@2)

.ENDMACRO

.MACRO CPI16

   cpi @0,low(@3)    ;Compare low byte

   ldi @2,high(@3)  ;

   cpc @1,@2       ;Compare high byte

.ENDMACRO


/*************************16 bit Signed Bubble Sort*****************************************

*@INPUT:RAM buffer with unsigned words to sort

*@USAGE:Z - pointer to buffer beginning

       rightl,righth - marks the last index 2 adjacent numbers have been exchanged

       cntl:cnth - index

       axl:axh,bxl:bxh - bytes to compare

       kxl:kxh - help variable

       

*@OUTPUT:RAM buffer sorted out!

*****************************************************************************************/

Signed16bitBubbleSort:

ldi    righth,low(INDEX_LIMIT16)    ;size of array - 1

mov rightl,righth

ldi righth,high(INDEX_LIMIT16)

sort16:

clr kl

clr kh


ldi    ZL,low(BUFFER16)

ldi    ZH,high(BUFFER16)

clr cntl

clr cnth

i_loop16:

ld axl,Z+

ld axh,Z+

ld bxl,Z

ldd bxh,Z+1

CP16 bxl,bxh,axl,axh

brge i_loop116;  signed

st -Z,bxh     ;exchange words

st -Z,bxl

adiw Z,2

st Z,axl

std Z+1,axh

mov kl,cntl

mov kh,cnth

i_loop116:

ADDI16 cntl,cnth,1

CP16 cntl,cnth,rightl,righth

brne i_loop16

mov rightl,kl

mov righth,kh

CPI16 rightl,righth,temp,0

brne sort16  

ret

Unsigned 2 byte Bubble sort.

/*************************16 bit Unsigned Selection Sort*****************************************

*@INPUT:RAM buffer with unsigned words to sort

*@USAGE:Z - pointer to buffer beginning/outer

       rightl,righth - outer loop index

       

        Y-pointer to buffer /inner

        cntl:cnth - inner loop index

        axl:axh,bxl:bxh - bytes to compare

       

        kxl:kxh - help variable

       

        temp

*@OUTPUT:RAM buffer sorted out!

*****************************************************************************************/

Unsigned16bitSelectionSort:

;j=0

ldi    rightl,0

ldi    righth,0

ldi    ZL,low(BUFFER16)

ldi    ZH,high(BUFFER16)

usort16:  

mov YL,ZL

mov YH,ZH


ld axl,Y+

ld axh,Y+


;iMin = j;

mov kl,rightl

mov kh,righth

mov cntl,rightl

mov cnth,righth

usi16_loop:

;i = j+1

ADDI16 cntl,cnth,1

ld bxl,Y+

ld bxh,Y+

CP16 bxl,bxh,axl,axh

brsh usi16_loop1  ;unsigned

; found new minimum; remember its index

mov axl,bxl

mov axh,bxh

mov kl,cntl

mov kh,cnth

usi16_loop1:

CPI16 cntl,cnth,temp,INDEX_LIMIT16

brlo usi16_loop

; iMin is the index of the minimum element. Swap it with the current position

CP16 kl,kh,rightl,righth

breq usi16_nextslot


;exchange then

ld bxl,Z

ldd bxh,Z+1

 

ldi    YL,low(BUFFER16)

ldi    YH,high(BUFFER16)

LSL16 kh,kl    ;multiply by 2 ->dealing with 2 bytes/word content

ADD16 YL,YH,kl,kh

ld axl,Y

ldd axh,Y+1

st Y,bxl

std Y+1,bxh

st Z,axl

std Z+1,axh





usi16_nextslot:  

CPI16 rightl,righth,temp,INDEX_LIMIT16-1;exlude the last one

breq usend16

   

adiw ZH:ZL,2

ADDI16 rightl,righth,1

rjmp usort16

usend16:
ret

Comments

Be the first to comment.




 Add Comment

  Comments 1 - 0 of 0  

Screen Name
Subject
Comment