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