Insertion sort

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

Comments

Be the first to comment.




 Add Comment

  Comments 1 - 0 of 0  

Screen Name
Subject
Comment