One of the simplest, yet efficient ways to sort an array is the insertion sort. It is another in- memory sorting algorithm which is quite useful in a restricted RAM environment like AVR CPU.
Insertion sort keeps making the left side of the array sorted until the whole array is sorted.
Basically, it investigates each element of the array to sort with the preceding sub-array of elements enclosed by first index and element’s index under investigation.
It swaps all elements positions until a smaller element is found.The rest of the subarray with smaller index positions is considered ordered.
Let us see an example of sorting an array to make the idea of insertion sort clearer, using AVR assembler to implement it.
Unordered list.
{12, 0, 13, 5, 16, 0, 17, 18}
Starting the outer iteration each element is compared with elements having an index smaller then the element under investigation.
No shift during the index #2 investigation.
Reposition of element of index #3 with index #1, all elements with indexes in between are shifted with one position to right.
No shift during the index #4 investigation.
Reposition of element of index #5 with index #1, all elements with indexes in between are shifted with one position to the right.
No shift happens for the rest of the array.
Implementation.
Avr assembler implementation is prepared for 8 and 16 bits signed and unsigned numbers.
Signed 1 byte Insertion sort.
/*
8-bit Insertion sort algorithm 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
.MACRO ADD16
add @0,@2 ;Add low bytes
adc @1,@3 ;Add high bytes with carry
.ENDMACRO
.MACRO ADDI16
subi @0,low(-@2)
sbci @1,high(-@2)
.ENDMACRO
/*************************8 bit Signed Insertion 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 array index
cnth:cntl - index counter
axl,bxl - bytes to compare
*@OUTPUT:RAM buffer sorted out!
*****************************************************************************************/
Signed8bitInsertionSort:
ldi right,0
clr cnth
sinsort:
cpi right,INDEX_LIMIT ;exlude the last one
breq sinend
inc right
mov cntl,right
ldi ZL,low(BUFFER)
ldi ZH,high(BUFFER)
ADD16 ZL,ZH,cntl,cnth
sinloop:
tst cntl ;d>0
breq sinsort
ld bxl,-Z
ldd axl,Z+1
cp axl,bxl ;array[d]
brge sinsort ;signed
std Z+1,bxl
st Z,axl
;d--
dec cntl
rjmp sinloop
sinend:
ret
Unsigned 1 byte Insertion sort.
/*************************8 bit Unsigned Insertion 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 array index
cnth:cntl - index counter
axl,bxl - bytes to compare
*@OUTPUT:RAM buffer sorted out!
*****************************************************************************************/
Unsigned8bitInsertionSort:
ldi right,0
clr cnth
uinsort:
cpi right,INDEX_LIMIT ;exlude the last one
breq uinend
inc right
mov cntl,right
ldi ZL,low(BUFFER)
ldi ZH,high(BUFFER)
ADD16 ZL,ZH,cntl,cnth
uinloop:
tst cntl ;d>0
breq uinsort
ld bxl,-Z
ldd axl,Z+1
cp axl,bxl ;array[d]
brsh uinsort ;unsigned
std Z+1,bxl
st Z,axl
;d--
dec cntl
rjmp uinloop
uinend:
ret
Signed 2 byte Insertion sort.
/*
*
* 16 bit insertion sort for signed/unsigned numbers.
* Author: Sergey Iliev
*/
#define BUFFER_SIZE16 512
#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
.MACRO ADD16
add @0,@2 ;Add low bytes
adc @1,@3 ;Add high bytes with carry
.ENDMACRO
.MACRO LSL16
lsl @1
rol @0
.ENDMACRO
/*************************16 bit Signed Insertion Sort*****************************************
*@INPUT:RAM buffer with unsigned words to sort
*@USAGE:Z - pointer to buffer beginning/outer
rightl,righth - outer loop index
cntl:cnth - inner loop index
axl:axh,bxl:bxh - bytes to compare
temp - temp variable
*@OUTPUT:RAM buffer sorted out!
*****************************************************************************************/
Signed16bitInsertionSort:
ldi rightl,0
ldi righth,0
sinsort16:
CPI16 rightl,righth,temp,INDEX_LIMIT16
breq sinend16
ADDI16 rightl,righth,1
mov cntl,rightl
mov cnth,righth
ldi ZL,low(BUFFER16)
ldi ZH,high(BUFFER16)
LSL16 cnth,cntl ;multiply by 2 ->dealing with 2 bytes/word content
ADD16 ZL,ZH,cntl,cnth
;restore content
mov cntl,rightl
mov cnth,righth
sinloop16:
CPI16 cntl,cnth,temp,0
breq sinsort16
;higher index number
ld axl,Z
ldd axh,Z+1
ld bxh,-Z
ld bxl,-Z
CP16 axl,axh,bxl,bxh ;array[d]
brge sinsort16 ;signed
st Z,axl
std Z+1,axh
std Z+2,bxl
std Z+3,bxh
;d--
ADDI16 cntl,cnth,-1
rjmp sinloop16
sinend16:
ret
Unsigned 2 byte Insertion sort.
/*************************16 bit Unsigned Insertion Sort*****************************************
*@INPUT:RAM buffer with unsigned words to sort
*@USAGE:Z - pointer to buffer beginning/outer
rightl,righth - outer loop index
cntl:cnth - inner loop index
axl:axh,bxl:bxh - bytes to compare
temp - temp variable
*@OUTPUT:RAM buffer sorted out!
*****************************************************************************************/
Unsigned16bitInsertionSort:
ldi rightl,0
ldi righth,0
uinsort16:
CPI16 rightl,righth,temp,INDEX_LIMIT16
breq uinend16
ADDI16 rightl,righth,1
mov cntl,rightl
mov cnth,righth
ldi ZL,low(BUFFER16)
ldi ZH,high(BUFFER16)
LSL16 cnth,cntl ;multiply by 2 ->dealing with 2 bytes/word content
ADD16 ZL,ZH,cntl,cnth
;restore content
mov cntl,rightl
mov cnth,righth
uinloop16:
CPI16 cntl,cnth,temp,0
breq uinsort16
;higher index number
ld axl,Z
ldd axh,Z+1
ld bxh,-Z
ld bxl,-Z
CP16 axl,axh,bxl,bxh ;array[d]
brsh uinsort16 ;unsigned
st Z,axl
std Z+1,axh
std Z+2,bxl
std Z+3,bxh
;d--
ADDI16 cntl,cnth,-1
rjmp uinloop16
uinend16:
ret