Bidirectional bubble sort

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.

/************************8 bit Unsigend 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 BUFFER_SIZE16  520

#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.

/******************16 bit Unsigned 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!
*****************************************************************************************/

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
Comments

Be the first to comment.




 Add Comment

  Comments 1 - 0 of 0  

Screen Name
Subject
Comment