Heap sort
Heapsort is another in place sorting algorithm suitable for small RAM devices.
Heap
The heap data structure is an array that is viewed as a binary tree. Fig.1 shows the heap
represented as a binary tree and a regular array. Each node of the tree corresponds to an
element of the array A[] that stores the value of the tree node.
The number above the node is the corresponding index in the array. The tree is logically viewed as
parent child construct as parents are always positioned to the left of their children.
A[1] is the root of the tree and given the index i of a node its parent PARENT(i) and left child LEFT(i)
and right child RIGHT(i) can be calculated by the following equations.
PARENT(i)
return [i/2]
LEFT(i)
return [2*i]
RIGHT(i)
return [2*i+1]
Heap property
Heap sort is based upon the so called heap property which for a max-heap(array is sorted from
left to right in increasing order) is represented by the following equation.
A[PARENT(i)]>=A[i]
in other words every node i other then the root, its value is at most the value of its parent thus the
largest value in a max-heap is stored at the root.
A min-heap is organized the opposite way but the implementation is for max-heap so it will not be discussed here.
Max-heapify procedure
Maintaining the max-heap property is an important part of the algorithm so here is a visual diagram of its inner working.
A[2] at node i=2 violate the max heap property since it is not larger then its both children(LEFT=A[4] and RIGHT=A[5])
The max heap property is restored by swapping A[2] with A[4], which in turn destroys the max heap property for node 4.
The max heap property is restored for node 4 but it destroyed the previously fixed property for node 2.
The recursive nature of the algorithm will fix it thus allowing the bigger values for this particular branch to
float up and smaller ones - float down.
Building the max-heap property for all nodes of the tree yields the following arrangement.
Heap sort
Now that the array is max-heap property compliant, the real sorting can begin.
Since the maximum value of the array floated up to the top, it can be put to its right position by
exchanging it with the last element(A[1] switches places with A[n]). Unfortunately the switch will destroy the max-heap
property of the tree for array element A[1]. All that is needed to restore max - heap property is to go through the same process
described above for array elements A[1] through A[n-1]. Observe that for each iteration the size of unordered elements in the
array decreases by 1.
The heap sort algorithm
repeats this process
until the subarray length of unsorted elements reaches 0.
The following is the implementation of heap sort in avr assembler for 8 and 16 bit signed/unsigned numbers.
Unsigned 8 bit heap sort
/*
------------------8 bit Unsigned Heap Sort----------------------------------
@INPUT BUFFER_SIZE - size of the buffer to sort
@USAGE: Z - pointer to RAM buffer element
Y - pointer to RAM buffer element
i - index
root - index helper
heapsize - index limit
axl,bxl - bytes to compare
@OUTPUT:RAM buffer sorted out!
----------------------------------------------------------------------------
*/
Unsigned8bitHeapSortEx:
//Building the heap (BUFFER_SIZE/2)
mov root,BUFFER_SIZE
lsr root
mov heapsize,BUFFER_SIZE
uforloop:
mov i,root
rcall Unsigned8maxheapify
dec root
cpi root,1
brsh uforloop
//heap sort
mov i,BUFFER_SIZE
mov root,BUFFER_SIZE
mov heapsize,BUFFER_SIZE
uheapsortloop:
//swap A[1] and A[i] ;first and last
ldi ZL,low(buffer)
ldi ZH,high(buffer)
adiw ZH:ZL,1
ld ax,-Z
ldi YL,low(buffer)
ldi YH,high(buffer)
clr temp
ADD16 YL,YH,root,temp
ld bx,-Y
st Z,bx
st Y,ax
//heap-size[A]=heap-size[A]-1
dec heapsize
ldi i,1
rcall Unsigned8maxheapify
dec root
cpi root,2
brsh uheapsortloop
ret
/******8 bit Unsigned Max Heapify****************
Maintain max-heap property for unsigned 8 bit
@INPUT heapsize - size of the sub-buffer to sort
i - index into the array
@USAGE: Z - pointer to RAM buffer element
Y - pointer to RAM buffer element
l - LEFT(i)
r - RIGHT(i)
temp,largest - temporary
axl,bxl - bytes to compare
@OUTPUT:Maintain heap property at A[i]
*/
Unsigned8maxheapify:
;check if lsl overflows the byte boundery
cpi i,0b10000000
brlo boundary
ret
boundary:
mov l,i
lsl l
mov r,i
lsl r
inc r
//if l<=heap_size[A]
cp heapsize,l
brlo umaxl
//A[l]
ldi ZL,low(buffer)
ldi ZH,high(buffer)
clr temp
ADD16 ZL,ZH,l,temp
ld ax,-Z
//A[i]
ldi ZL,low(buffer)
ldi ZH,high(buffer)
clr temp
ADD16 ZL,ZH,i,temp
ld bx,-Z
//if A[i]<A[l]
cp bx,ax
brsh umaxl
mov largest,l
rjmp umaxlon
umaxl: //largest<-i
mov largest,i
umaxlon:
//do the same for the right
//if r<=heap_size[A]
cp heapsize,r
brlo umaxr
//A[r]
ldi ZL,low(buffer)
ldi ZH,high(buffer)
clr temp
ADD16 ZL,ZH,r,temp
ld ax,-Z
//A[largest]
ldi ZL,low(buffer)
ldi ZH,high(buffer)
clr temp
ADD16 ZL,ZH,largest,temp
ld bx,-Z
//A[r]>A[largest]
cp bx,ax
brsh umaxr
mov largest,r
umaxr:
//if largest!=i
cp largest,i
breq umaxend
//swap
ldi ZL,low(buffer)
ldi ZH,high(buffer)
clr temp
ADD16 ZL,ZH,i,temp
ld ax,-Z
ldi YL,low(buffer)
ldi YH,high(buffer)
clr temp
ADD16 YL,YH,largest,temp
ld bx,-Y
st Z,bx
st Y,ax
//prepare next iteration
mov i,largest
rjmp Unsigned8maxheapify
umaxend:
ret
Signed 8 bit heap sort
/*
------------------8 bit Signed Heap Sort----------------------------------
@INPUT BUFFER_SIZE - size of the buffer to sort
@USAGE: Z - pointer to RAM buffer element
Y - pointer to RAM buffer element
i - index
root - index helper
heapsize - index limit
axl,bxl - bytes to compare
@OUTPUT:RAM buffer sorted out!
----------------------------------------------------------------------------
*/
Signed8bitHeapSortEx:
mov root,BUFFER_SIZE
lsr root
mov heapsize,BUFFER_SIZE
sforloop: //BUILD MAX HEAP
mov i,root
rcall Signed8maxheapify
dec root
cpi root,1
brsh sforloop
//heap sort
mov i,BUFFER_SIZE
mov root,BUFFER_SIZE
mov heapsize,BUFFER_SIZE
sheapsortloop:
//swap A[1] and A[i] ;first and last
ldi ZL,low(buffer)
ldi ZH,high(buffer)
adiw ZH:ZL,1
ld ax,-Z
ldi YL,low(buffer)
ldi YH,high(buffer)
clr temp
ADD16 YL,YH,root,temp
ld bx,-Y
st Z,bx
st Y,ax
//heap-size[A]=heap-size[A]-1
dec heapsize
ldi i,1
rcall Signed8maxheapify
dec root
cpi root,2
brsh sheapsortloop
ret
/******8 bit Signed Max Heapify****************
Maintain max-heap property for signed 8 bit
@INPUT heapsize - size of the sub-buffer to sort
i - index into the array
@USAGE: Z - pointer to RAM buffer element
Y - pointer to RAM buffer element
l - LEFT(i)
r - RIGHT(i)
temp,largest - temporary
axl,bxl - bytes to compare
@OUTPUT:Maintain heap property at A[i]
*/
Signed8maxheapify:
;check if lsl overflows the byte boundery
cpi i,0b10000000
brlo sboundary
ret
sboundary:
mov l,i
lsl l
mov r,i
lsl r
inc r
//if l<=heap_size[A]
cp heapsize,l
brlo smaxl
//A[l]
ldi ZL,low(buffer)
ldi ZH,high(buffer)
clr temp
ADD16 ZL,ZH,l,temp
ld ax,-Z
//A[i]
ldi ZL,low(buffer)
ldi ZH,high(buffer)
clr temp
ADD16 ZL,ZH,i,temp
ld bx,-Z
//if A[i]<A[l]
cp bx,ax
brge smaxl //signed
mov largest,l
rjmp smaxlon
smaxl: //largest<-i
mov largest,i
smaxlon:
//do the same for the right
//if r<=heap_size[A]
cp heapsize,r
brlo smaxr
//A[r]
ldi ZL,low(buffer)
ldi ZH,high(buffer)
clr temp
ADD16 ZL,ZH,r,temp
ld ax,-Z
//A[largest]
ldi ZL,low(buffer)
ldi ZH,high(buffer)
clr temp
ADD16 ZL,ZH,largest,temp
ld bx,-Z
//A[r]>A[largest]
cp bx,ax
brge smaxr //signed
mov largest,r
smaxr:
//if largest!=i
cp largest,i
breq smaxend
//swap
ldi ZL,low(buffer)
ldi ZH,high(buffer)
clr temp
ADD16 ZL,ZH,i,temp
ld ax,-Z
ldi YL,low(buffer)
ldi YH,high(buffer)
clr temp
ADD16 YL,YH,largest,temp
ld bx,-Y
st Z,bx
st Y,ax
//prepare next iteration
mov i,largest
rjmp Signed8maxheapify
smaxend:
ret
Unsigned 16 bit heap sort
/*
------------------16 bit Unsigned Heap Sort----------------------------------
@INPUT buffersize - 2 byte long number up to 2^16
@USAGE: Z - pointer to RAM buffer element
Y - pointer to RAM buffer element
i - index
root - index helper
heapsize - index limit
a,b - number to compare
@OUTPUT:RAM buffer sorted out!
----------------------------------------------------------------------------
*/
Unsigned16bitHeapSortEx:
//i=lenght[A]/2
mov rootl,buffersizel
mov rooth,buffersizeh
LSR16 ih,il ;devide by 2
mov heapsizel,buffersizel
mov heapsizeh,buffersizeh
uforloop:
mov il,rootl
mov ih,rooth
rcall Unsigned16maxheapify
ADDI16 rootl,rooth,-1 ;decrement by 1
CPI16 rootl,rooth,temp,1 ;temp is temporary and destroyed
brsh uforloop
//heap sort
mov il,buffersizel
mov il,buffersizeh
mov rootl,buffersizel
mov rooth,buffersizeh
mov heapsizel,buffersizel
mov heapsizeh,buffersizeh
uheapsortloop:
//swap A[1] and A[i] ;first and last
ldi ZL,low(buffer16)
ldi ZH,high(buffer16)
adiw ZH:ZL,2 ;2 byte number
ld ah,-Z
ld al,-Z
ldi YL,low(buffer16)
ldi YH,high(buffer16)
mov templ,rootl
mov temph,rooth
LSL16 temph,templ
ADD16 YL,YH,templ,temph
ld bh,-Y
ld bl,-Y
//swap
st Z,bl
std Z+1,bh
st Y,al
std Y+1,ah
//heap-size[A]=heap-size[A]-1
ADDI16 heapsizel,heapsizeh,-1
ldi il,1
ldi ih,0
rcall Unsigned16maxheapify
ADDI16 rootl,rooth,-1
CPI16 rootl,rooth,temp,2
brsh uheapsortloop
ret
/******16 bit Unsigned Max Heapify****************
Maintain max-heap property for unsigned 16 bit
@INPUT heapsize - size of the sub-buffer to sort
i - index into the array
@USAGE: Z - pointer to RAM buffer element
Y - pointer to RAM buffer element
l - LEFT(i)
r - RIGHT(i)
temp,largest - temporary
ax,bx - bytes to compare
@OUTPUT:Maintain heap property at A[i]
*/
Unsigned16maxheapify:
;check if lsl overflows the word boundery
CPI16 il,ih,temp,32768 ;0x8000
brlo boundary
ret
boundary:
mov ll,il
mov lh,ih
LSL16 lh,ll ;LEFT index
mov rl,il
mov rh,ih
LSL16 rh,rl
ADDI16 rl,rh,1 ;RIGHT index
//if l<=heap_size[A]
CP16 heapsizel,heapsizeh,ll,lh
brlo umaxl
//A[l]
ldi ZL,low(buffer16)
ldi ZH,high(buffer16)
//dealing with 2 byte size number
mov templ,ll
mov temph,lh
LSL16 temph,templ
ADD16 ZL,ZH,templ,temph
ld ah,-Z
ld al,-Z
//A[i]
ldi ZL,low(buffer16)
ldi ZH,high(buffer16)
mov templ,il
mov temph,ih
LSL16 temph,templ
ADD16 ZL,ZH,templ,temph
ld bh,-Z
ld bl,-Z
//if A[i]<A[l]
CP16 bl,bh,al,ah
brsh umaxl
mov largestl,ll //largest<-l
mov largesth,lh
rjmp umaxlon
umaxl: //largest<-i
mov largestl,il
mov largesth,ih
umaxlon:
//do the same for the right
//if r<=heap_size[A]
CP16 heapsizel,heapsizeh,rl,rh
brlo umaxr
//A[r]
ldi ZL,low(buffer16)
ldi ZH,high(buffer16)
//dealing with 2 byte size number
mov templ,rl
mov temph,rh
LSL16 temph,templ
ADD16 ZL,ZH,templ,temph
ld ah,-Z
ld al,-Z
//A[largest]
ldi ZL,low(buffer16)
ldi ZH,high(buffer16)
mov templ,largestl
mov temph,largesth
LSL16 temph,templ
ADD16 ZL,ZH,templ,temph
ld bh,-Z
ld bl,-Z
//A[r]>A[largest]
CP16 bl,bh,al,ah
brsh umaxr ;largest<-r
mov largestl,rl
mov largesth,rh
umaxr:
//if largest!=i
CP16 largestl,largesth,il,ih
breq umaxend
//swap
ldi ZL,low(buffer16)
ldi ZH,high(buffer16)
mov templ,il
mov temph,ih
LSL16 temph,templ
ADD16 ZL,ZH,templ,temph
ld ah,-Z
ld al,-Z
ldi YL,low(buffer16)
ldi YH,high(buffer16)
mov templ,largestl
mov temph,largesth
LSL16 temph,templ
ADD16 YL,YH,templ,temph
ld bh,-Y
ld bl,-Y
st Z,bl
std Z+1,bh
st Y,al
std Y+1,ah
//prepare next iteration
mov il,largestl
mov ih,largesth
rjmp Unsigned16maxheapify
umaxend:
ret
Signed 16 bit heap sort
/*
------------------16 bit Signed Heap Sort----------------------------------
@INPUT buffersize - 2 byte long number up to 2^16
@USAGE: Z - pointer to RAM buffer element
Y - pointer to RAM buffer element
i - index
root - index helper
heapsize - index limit
a,b - number to compare
@OUTPUT:RAM buffer sorted out!
----------------------------------------------------------------------------
*/
Signed16bitHeapSortEx:
//i=lenght[A]/2
mov rootl,buffersizel
mov rooth,buffersizeh
LSR16 ih,il ;devide by 2
mov heapsizel,buffersizel
mov heapsizeh,buffersizeh
//hepify
sforloop:
mov il,rootl
mov ih,rooth
rcall Signed16maxheapify
ADDI16 rootl,rooth,-1 ;decrement by 1
CPI16 rootl,rooth,temp,1 ;temp is temporary and destroyed
brsh sforloop
//heap sort
;mov il,buffersizel
;mov il,buffersizeh
mov rootl,buffersizel
mov rooth,buffersizeh
mov heapsizel,buffersizel
mov heapsizeh,buffersizeh
sheapsortloop:
//swap A[1] and A[i] ;first and last
ldi ZL,low(buffer16)
ldi ZH,high(buffer16)
adiw ZH:ZL,2 ;2 byte number
ld ah,-Z
ld al,-Z
ldi YL,low(buffer16)
ldi YH,high(buffer16)
mov templ,rootl
mov temph,rooth
LSL16 temph,templ
ADD16 YL,YH,templ,temph
ld bh,-Y
ld bl,-Y
//swap
st Z,bl
std Z+1,bh
st Y,al
std Y+1,ah
//heap-size[A]=heap-size[A]-1
ADDI16 heapsizel,heapsizeh,-1
ldi il,1
ldi ih,0
rcall Signed16maxheapify
ADDI16 rootl,rooth,-1
CPI16 rootl,rooth,temp,2
brsh sheapsortloop
ret
/******16 bit Signed Max Heapify****************
Maintain max-heap property for signed 16 bit
@INPUT heapsize - size of the sub-buffer to sort
i - index into the array
@USAGE: Z - pointer to RAM buffer element
Y - pointer to RAM buffer element
l - LEFT(i)
r - RIGHT(i)
temp,largest - temporary
ax,bx - bytes to compare
@OUTPUT:Maintain heap property at A[i]
*/
Signed16maxheapify:
;check if lsl overflows the word boundery
CPI16 il,ih,temp,32768 ;0x8000
brlo sboundary
ret
sboundary:
mov ll,il
mov lh,ih
LSL16 lh,ll ;LEFT index
mov rl,il
mov rh,ih
LSL16 rh,rl
ADDI16 rl,rh,1 ;RIGHT index
//if l<=heap_size[A]
CP16 heapsizel,heapsizeh,ll,lh
brlo smaxl
//A[l]
ldi ZL,low(buffer16)
ldi ZH,high(buffer16)
//dealing with 2 byte size number
mov templ,ll
mov temph,lh
LSL16 temph,templ
ADD16 ZL,ZH,templ,temph
ld ah,-Z
ld al,-Z
//A[i]
ldi ZL,low(buffer16)
ldi ZH,high(buffer16)
mov templ,il
mov temph,ih
LSL16 temph,templ
ADD16 ZL,ZH,templ,temph
ld bh,-Z
ld bl,-Z
//if A[i]<A[l]
CP16 bl,bh,al,ah
brge smaxl //signed
mov largestl,ll //largest<-l
mov largesth,lh
rjmp smaxlon
smaxl: //largest<-i
mov largestl,il
mov largesth,ih
smaxlon:
//do the same for the right
//if r<=heap_size[A]
CP16 heapsizel,heapsizeh,rl,rh
brlo smaxr
//A[r]
ldi ZL,low(buffer16)
ldi ZH,high(buffer16)
//dealing with 2 byte size number
mov templ,rl
mov temph,rh
LSL16 temph,templ
ADD16 ZL,ZH,templ,temph
ld ah,-Z
ld al,-Z
//A[largest]
ldi ZL,low(buffer16)
ldi ZH,high(buffer16)
mov templ,largestl
mov temph,largesth
LSL16 temph,templ
ADD16 ZL,ZH,templ,temph
ld bh,-Z
ld bl,-Z
//A[r]>A[largest]
CP16 bl,bh,al,ah
brge smaxr ;signed;largest<-r
mov largestl,rl
mov largesth,rh
smaxr:
//if largest!=i
CP16 largestl,largesth,il,ih
breq smaxend
//swap
ldi ZL,low(buffer16)
ldi ZH,high(buffer16)
mov templ,il
mov temph,ih
LSL16 temph,templ
ADD16 ZL,ZH,templ,temph
ld ah,-Z
ld al,-Z
ldi YL,low(buffer16)
ldi YH,high(buffer16)
mov templ,largestl
mov temph,largesth
LSL16 temph,templ
ADD16 YL,YH,templ,temph
ld bh,-Y
ld bl,-Y
st Z,bl
std Z+1,bh
st Y,al
std Y+1,ah
//prepare next iteration
mov il,largestl
mov ih,largesth
rjmp Signed16maxheapify
smaxend:
ret
Helper macros
.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 MSB,LSB
.MACRO LSL16
lsl @1
rol @0
.ENDMACRO
;@MACRO LSR16 MSB,LSB
.MACRO LSR16
lsr @0
ror @1
.ENDMACRO