Selection sort

Selection sort is a sorting algorithm that does not require additional storage place and is therefore called “in place sorting”. This feature is particularly useful for devices with limited RAM storage as are AVR microprocessors.

The algorithm goes through each array’s element index and logically divides the array to 2 parts - sorted one and unsorted one as the element itself is the boundary between the 2 logical subarrays. The left logical subarray is sorted one and the right one is unsorted. The algorithm investigates the right unsorted array for the smallest element and swaps it, if it finds one, with the boundary element. Same is done for the next element of the array until the end is reached.With each iteration the boundary index is shifted with one position towards the end of the unsorted subarray.

Let us see an example of sorting an array to make the idea of selection sort clearer.
{25, 0, 13, -5, 16, 0, 1, 14}

At the beginning the array is unsorted so the first element is the boundary number 25(red).

The subarray in orange is the unsorted one to iterate, looking for the smallest compared to the boundary element. Number -5(yellow) is the smallest and smaller to 25 so a swap is activated.
Move to the next element 0(red) and iterating through the unsorted subarray, we can see that there is no smaller number then the boundary number so no swap is activated.Moving on...

Number 0(yellow) is the smallest in the unsorted subarray and smaller then the boundary number 13(red) so a swap is activated.

Loop goes on  until the unsorted subarray is depleted.

Avr assembler implementation is prepared for 8  and 16 bits signed and unsigned numbers.



Signed 1 byte Selection sort.


/*
8-bit Selection sort algorithm for signed/unsigned numbers up to 256 values.
@AUTHOR:Sergey Iliev/Sofia
*/

#define BUFFER_SIZE 58

#define INDEX_LIMIT BUFFER_SIZE-1   ;zero based index

.dseg
buffer:  .byte BUFFER_SIZE
.cseg

/***********************8 bit Sigend Selection Sort*************
;Sort signed bytes between -128 and 127
@INPUT:RAM buffer to sort
@USAGE: right,k,cnt,axl,bxl,
        Z - buffer item pointer
        Y - buffer item pointer
@OUTPUT: RAM buffer sorted out
****************************************************************/
Signed8bitSelectionSort:
 ldi    right,0
ssort:
   
 ldi    ZL,low(BUFFER)
 ldi    ZH,high(BUFFER)

 clr k
 ADD16 ZL,ZH,right,k

 ;load index minimum
 ld axl,Z

 mov k,right
 mov cnt,right

ssi_loop:
 ld bxl,Z+
 cp bxl,axl       ;looking for the index of lowest value
 brge ssi_loop1      ;signed      

 mov k,cnt  
 mov axl,bxl

ssi_loop1:
 inc cnt
 cpi cnt,BUFFER_SIZE
 brne ssi_loop       

 ;exchange if <>
 cp k,right
 breq ssi_nextslot

 
 clr cnt
 
 ldi    ZL,low(BUFFER)
 ldi    ZH,high(BUFFER)
 
 ADD16 ZL,ZH,k,cnt  
 ld bxl,Z
 
 ldi    YL,low(BUFFER)
 ldi    YH,high(BUFFER)
 
 
 ADD16 YL,YH,right,cnt
 ld axl,Y
 

 st Y,bxl
 st Z,axl
 
 
   

ssi_nextslot:
 cpi right,INDEX_LIMIT-1   ;exlude the last one
 breq ssend  
 inc right
 rjmp ssort
 
ssend:
ret

Unsigned 1 byte Selection sort.


/************************8 bit Unsigend Selection Sort*************
;Sort unsigned bytes between 0 and 255
@INPUT:RAM buffer to sort
@USAGE: right,k,cnt,axl,bxl,
        Z - buffer item pointer
        Y - buffer item pointer
@OUTPUT: RAM buffer sorted out
**************************************************************/

Unsigned8bitSelectionSort:
 ldi    right,0
ussort:
   
 ldi    ZL,low(BUFFER)
 ldi    ZH,high(BUFFER)

 clr k
 ADD16 ZL,ZH,right,k

 ;load index minimum
 ld axl,Z

 mov k,right
 mov cnt,right

si_loop:
 ld bxl,Z+
 cp bxl,axl       ;looking for the index of lowest value
 brsh si_loop1    ;unsigned

 mov k,cnt  
 mov axl,bxl

si_loop1:
 inc cnt
 cpi cnt,BUFFER_SIZE
 brne si_loop  

 ;exchange if <>
 cp k,right
 breq si_nextslot

 
 clr cnt
 
 ldi    ZL,low(BUFFER)
 ldi    ZH,high(BUFFER)
 
 ADD16 ZL,ZH,k,cnt  
 ld bxl,Z
 
 ldi    YL,low(BUFFER)
 ldi    YH,high(BUFFER)
 
 
 ADD16 YL,YH,right,cnt
 ld axl,Y
 

 st Y,bxl
 st Z,axl
 
 
   

si_nextslot:
 cpi right,INDEX_LIMIT-1   ;exlude the last one
 breq send  
 inc right
 rjmp ussort
 
send:
 
ret

Signed 2 byte Selection sort.

/**********************************************************************
16 bit selection sort for signed/unsigned numbers up to 32768 numbers
@AUTHOR:Sergey Iliev/Sofia
***********************************************************************/

#define BUFFER_SIZE16 521  ;582

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

.MACRO CPI16
    cpi @0,low(@3)    ;Compare low byte
    ldi @2,high(@3)  ;
    cpc @1,@2       ;Compare high byte
.ENDMACRO

;@MACRO LSL16 MSB,LSB
.MACRO LSL16
 lsl @1
 rol @0
.ENDMACRO

/*************************16 bit Signed Selection Sort*****************************************
*@INPUT:RAM buffer with signed 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!
*****************************************************************************************/

Signed16bitSelectionSort:
 ;j=0
 ldi    rightl,0
 ldi    righth,0

 ldi    ZL,low(BUFFER16)
 ldi    ZH,high(BUFFER16)

ssort16:  
 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

ssi16_loop:
;i = j+1
 ADDI16 cntl,cnth,1
 
 ld bxl,Y+
 ld bxh,Y+

 CP16 bxl,bxh,axl,axh
 brge ssi16_loop1

; found new minimum; remember its index
 mov axl,bxl
 mov axh,bxh

 mov kl,cntl
 mov kh,cnth

ssi16_loop1:
 CPI16 cntl,cnth,temp,INDEX_LIMIT16
 brlo ssi16_loop

; iMin is the index of the minimum element. Swap it with the current position
 CP16 kl,kh,rightl,righth
 breq ssi16_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





ssi16_nextslot:  
 CPI16 rightl,righth,temp,INDEX_LIMIT16-1;exlude the last one
 breq ssend16
    
 adiw ZH:ZL,2
 ADDI16 rightl,righth,1
 
 rjmp ssort16

ssend16:
ret

Unsigned 2 byte Selection 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


Comments

Be the first to comment.




 Add Comment

  Comments 1 - 0 of 0  

Screen Name
Subject
Comment