Bidirectional bubble sort is a variation to the well known bubble sort but adds an extra level of efficiency in terms of speed.
It iterates through the list of elements not only from the beginning to the end as the bubble sort does but also from the end to beginning in reverse order, reducing the overall sorting time by dynamically limiting the number of elements being iterated through.
It is also known as cocktail shaker sort, shaker sort, double-direction bubble sort and is also an “in place sorting algorithm” which means that no extra RAM memory is needed to sort the list elements.
The bidirectional bubble sort works by (1)iterating up the array to be sorted from the first element to the last, comparing each pair of elements and swapping their positions if necessary. The last swap index position is remembered to become the next upper limit of forward iteration.(2)Right after the forward iteration, follows a backward iteration starting from last upper index down to the lower index limit comparing each pair of elements and swapping their positions if necessary.The last swap index position is remembered to become the next lower limit of the backward iteration.The whole 2 step cycle repeats itself until the two limits - upper and lower - become equal.
Let us see an example of sorting an array to make the idea of bidirectional bubble sort clearer, using AVR assembler to implement it.
Unordered list.
{12, 0, 13, 5, 16, 0, 17, 18}
Forward iteration.
During the first forward iteration the initial upper and lower limits are index #7 and #0 respectively. The iteration will start from the lower index limit which happens to be #0 in the beginning.
Number 16 will bubble up, swapping up since it is the biggest number in the iteration.The iteration will stop when the upper index limit is reached.
As a result the upper index limit will change to #5(the last index where a swap happened) as indexes above it are already sorted.
Backward iteration.
The backward iteration starts from the upper index limit down to lower index limit swapping adjacent numbers if necessary.
Number 0(index #4) will bubble down, swapping all the way down since it is the smallest number in this iteration.
As a result the lower index limit will change to #1(the last index where a swap happened) as indexes under it are already sorted.
The same sequence of forward and backward iteration repeats until the lower and upper index limit become the same(equal).
Implementation.
Avr assembler implementation is prepared for 8 and 16 bits signed and unsigned numbers.
Signed 1 byte Bi-Directional Bubble sort.
#define BUFFER_SIZE 256
#define INDEX_LIMIT BUFFER_SIZE-1 ;zero based index
.dseg
buffer: .byte BUFFER_SIZE
.cseg
/************************8 bit Sigend Bi-directional Bubble Sort*************
;Sort unsigned bytes between 0 and 255
@AUTHOR: Sergey Iliev
@INPUT:RAM buffer to sort
@USAGE: right,left,k,cnt,axl,bxl,
Z - buffer item pointer
@OUTPUT: RAM buffer sorted out
**************************************************************/
Signed8bitBiDirectBubbleSort:
ldi right,INDEX_LIMIT ;size of array - 1
ldi left,0
sbbsort:
clr k
;first loop iterate forward
ldi ZL,low(BUFFER)
ldi ZH,high(BUFFER)
clr temp
mov cnt,left
ADD16 ZL,ZH,cnt,temp
sbb_loopr:
ld axl,Z+
ld bxl,Z
cp bxl,axl
brge sbb_loopr1 ;signed
st -Z,bxl
adiw Z,1
st Z,axl
mov k,cnt
sbb_loopr1:
inc cnt
cp cnt,right
brlo sbb_loopr
mov right,k
ldi cnt,INDEX_LIMIT
mov k,cnt
;exit if no sawp happened or first position swap
tst right
brne sbb_loopl0
ret
sbb_loopl0:
;second loop iterate backward
ldi ZL,low(BUFFER)
ldi ZH,high(BUFFER)
clr temp
mov cnt,right
ADD16 ZL,ZH,cnt,temp
sbb_loopl:
ld axl,Z
ld bxl,-Z
cp bxl,axl
brlt sbb_loopl1 ;signed
st Z,axl
std Z+1,bxl
mov k,cnt
sbb_loopl1:
dec cnt
cp left,cnt
brlo sbb_loopl
mov left,k
cp left,right
brlo sbbsort
ret
Unsigned 1 byte Bi-Directional Bubble sort.
;Sort unsigned bytes between 0 and 255
@AUTHOR: Sergey Iliev
@INPUT:RAM buffer to sort
@USAGE: right,left,k,cnt,axl,bxl,
Z - buffer item pointer
@OUTPUT: RAM buffer sorted out
**************************************************************/
Unsigned8bitBiDirectBubbleSort:
ldi right,INDEX_LIMIT ;size of array - 1
ldi left,0
ubbsort:
clr k
;first loop iterate forward
ldi ZL,low(BUFFER)
ldi ZH,high(BUFFER)
clr temp
mov cnt,left
ADD16 ZL,ZH,cnt,temp
ubb_loopr:
ld axl,Z+
ld bxl,Z
cp bxl,axl
brsh ubb_loopr1 ;unsigned
st -Z,bxl
adiw Z,1
st Z,axl
mov k,cnt
ubb_loopr1:
inc cnt
cp cnt,right
brlo ubb_loopr
mov right,k
ldi cnt,INDEX_LIMIT
mov k,cnt
;exit if no sawp happened or first position swap
tst right
brne ubb_loopl0
ret
ubb_loopl0:
;second loop iterate backward
ldi ZL,low(BUFFER)
ldi ZH,high(BUFFER)
clr temp
mov cnt,right
ADD16 ZL,ZH,cnt,temp
ubb_loopl:
ld axl,Z
ld bxl,-Z
cp bxl,axl
brlo ubb_loopl1 ;unsigned
st Z,axl
std Z+1,bxl
mov k,cnt
ubb_loopl1:
dec cnt
cp left,cnt
brlo ubb_loopl
mov left,k
cp left,right
brlo ubbsort
ret
Signed 2 byte Bi-Directional Bubble sort.
#define INDEX_LIMIT16 BUFFER_SIZE16-1 ;zero based index
.dseg
buffer16: .byte BUFFER_SIZE16*2
.cseg
/****************16 bit Signed Bi-Directional Bubble/Coctail/Shuffle Sort************
*@AUTHOR: Sergey Iliev
*@INPUT:RAM buffer with unsigned words to sort
*@USAGE:Z - pointer to buffer beginning
rightl,righth - marks the last index(rightmost) 2 adjacent numbers have been exchanged
leftl,lefth - marks the last index(leftmost) 2 adjacent numbers have been exchanged
cntl:cnth - index
axl:axh,bxl:bxh - words to compare
kxl:kxh - help variable
*@OUTPUT:RAM buffer sorted out!
*****************************************************************************************/
Signed16bitBiDirectBubbleSort:
ldi rightl,low(INDEX_LIMIT16) ;size of array - 1
ldi righth,high(INDEX_LIMIT16)
//set lower address boundery
ldi leftl,low(0)
ldi lefth,high(0)
sbbsort16:
;prepare for left to right itteration
clr kh
clr kl
;first loop iterate forward
ldi ZL,low(BUFFER16)
ldi ZH,high(BUFFER16)
mov cnth,lefth
mov cntl,leftl
;position to the left-most un-ordered element
LSL16 cnth,cntl ;multiply by 2 ->dealing with 2 bytes/word content
ADD16 ZL,ZH,cntl,cnth
;restore cnt
mov cnth,lefth
mov cntl,leftl
sbb_loopr16:
ld axl,Z+
ld axh,Z+
ld bxl,Z
ldd bxh,Z+1
CP16 bxl,bxh,axl,axh
brge sbb_loopr116 ;signed
st -Z,bxh ;exchange words
st -Z,bxl
adiw Z,2
st Z,axl
std Z+1,axh
;remember last rightmost unordered position
mov kl,cntl
mov kh,cnth
sbb_loopr116:
ADDI16 cntl,cnth,1
;did it get to the last previously unordered position
CP16 cntl,cnth,rightl,righth
brlo sbb_loopr16
mov rightl,kl
mov righth,kh
;exit if no sawp happened or first position swap
CPI16 rightl,righth,cntl,0
brne sbb_loopl0
ret
;----------------reverse iteration----------------------------
sbb_loopl0:
;prepare for the right to left iterration
ldi ZL,low(BUFFER16)
ldi ZH,high(BUFFER16)
mov kl,rightl
mov kh,righth
mov cntl,rightl
mov cnth,righth
;second loop iterate backward
LSL16 cnth,cntl ;multiply by 2 ->dealing with 2 bytes/word content
ADD16 ZL,ZH,cntl,cnth
//restore cnt
mov cntl,rightl
mov cnth,righth
sbb_loopl16:
ldd axh,Z+1
ld axl,Z
ld bxh,-Z
ld bxl,-Z
CP16 bxl,bxh,axl,axh
brlt sbb_loopl116 ;signed
st Z+,axl
st Z+,axh
st Z,bxl
std Z+1,bxh
ADDI16 ZL,ZH,-2
;remember last leftmost unordered position
mov kl,cntl
mov kh,cnth
sbb_loopl116:
ADDI16 cntl,cnth,-1
;did it get to the last previously unordered position
CP16 leftl,lefth,cntl,cnth
brlo sbb_loopl16
mov leftl,kl
mov lefth,kh
CP16 leftl,lefth,rightl,righth
brlo asbbsort16
ret
asbbsort16:
rjmp sbbsort16
Unsigned 2 byte Bi-Directional Bubble sort.
*@AUTHOR: Sergey Iliev
*@INPUT:RAM buffer with unsigned words to sort
*@USAGE:Z - pointer to buffer beginning
rightl,righth - marks the last index(rightmost) 2 adjacent numbers have been exchanged
leftl,lefth - marks the last index(leftmost) 2 adjacent numbers have been exchanged
cntl:cnth - index
axl:axh,bxl:bxh - words to compare
kxl:kxh - help variable
*@OUTPUT:RAM buffer sorted out!
*****************************************************************************************/
Unsigned16bitBiDirectBubbleSort:
ldi rightl,low(INDEX_LIMIT16) ;size of array - 1
ldi righth,high(INDEX_LIMIT16)
//set lower address boundery
ldi leftl,low(0)
ldi lefth,high(0)
ubbsort16:
;prepare for left to right itteration
clr kh
clr kl
;first loop iterate forward
ldi ZL,low(BUFFER16)
ldi ZH,high(BUFFER16)
mov cnth,lefth
mov cntl,leftl
;position to the left-most un-ordered element
LSL16 cnth,cntl ;multiply by 2 ->dealing with 2 bytes/word content
ADD16 ZL,ZH,cntl,cnth
;restore cnt
mov cnth,lefth
mov cntl,leftl
ubb_loopr16:
ld axl,Z+
ld axh,Z+
ld bxl,Z
ldd bxh,Z+1
CP16 bxl,bxh,axl,axh
brsh ubb_loopr116 ;unsigned
st -Z,bxh ;exchange words
st -Z,bxl
adiw Z,2
st Z,axl
std Z+1,axh
;remember last rightmost unordered position
mov kl,cntl
mov kh,cnth
ubb_loopr116:
ADDI16 cntl,cnth,1
;did it get to the last previously unordered position
CP16 cntl,cnth,rightl,righth
brlo ubb_loopr16
mov rightl,kl
mov righth,kh
;exit if no sawp happened or first position swap
CPI16 rightl,righth,cntl,0
brne ubb_loopl0
ret
;----------------reverse iteration----------------------------
ubb_loopl0:
;prepare for the right to left iterration
ldi ZL,low(BUFFER16)
ldi ZH,high(BUFFER16)
mov kl,rightl
mov kh,righth
mov cntl,rightl
mov cnth,righth
;second loop iterate backward
LSL16 cnth,cntl ;multiply by 2 ->dealing with 2 bytes/word content
ADD16 ZL,ZH,cntl,cnth
//restore cnt
mov cntl,rightl
mov cnth,righth
ubb_loopl16:
ldd axh,Z+1
ld axl,Z
ld bxh,-Z
ld bxl,-Z
CP16 bxl,bxh,axl,axh
brlo ubb_loopl116 ;unsigned
st Z+,axl
st Z+,axh
st Z,bxl
std Z+1,bxh
ADDI16 ZL,ZH,-2
;remember last leftmost unordered position
mov kl,cntl
mov kh,cnth
ubb_loopl116:
ADDI16 cntl,cnth,-1
;did it get to the last previously unordered position
CP16 leftl,lefth,cntl,cnth
brlo ubb_loopl16
mov leftl,kl
mov lefth,kh
CP16 leftl,lefth,rightl,righth
brlo aubbsort16
ret
aubbsort16:
rjmp ubbsort16