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