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

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)

ld bxl,Z

ldi    YL,low(BUFFER)
ldi    YH,high(BUFFER)

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

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)

ld bxl,Z

ldi    YL,low(BUFFER)
ldi    YH,high(BUFFER)

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

.ENDMACRO

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

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

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

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

rjmp usort16

usend16:
ret