; 
; SORT is a programming example of sorting by "Straight Selection" 
; on the DSP56001. SORT uses the straight selection algorithm to sort  
; an ARRAY of signed numbers.  The sort is performed "in-place" and  
; requires no additional memory locations.  The algorithm searches all  
; items of the array to find the lowest valued item which is swapped  
; with the next item of the final sorted sequence.
; 
; The execution time is proportional to the square of the array size  
; (N_ITEMS).  SORT is efficient for sorting smaller arrays of numbers. 
; 
; Written by K.Y.Khoo based on the program sort1.asm and sort1t.asm from  
; the Motorola DSP bulletin board. 
; 
; Last Updated: 3 Oct 95 
; 
        page    132,66,3,3 
        opt     nomd,mex,cre,cex,mu,rc 
 
        org     x:$10 
ARRAY   dc      44,55,12,42,94,18,06,67 
N_ITEMS equ     8       
; 
; ARRAY = location of an array of numbers in X memory space, 
;         first item is located at ARRAY. 
; N_ITEMS = number of items in the array 
; 
; register usage: 
;       altered: a, b, y0, r0, r1, r2, r4, n1
;       uses 4 words of stack 
;       assumes m0..m2 = $ffff 
; 
        org     p:$0        ; reset vector
        jmp     start 
 
        org     p:$40       ; start of program
start 
        move    #N_ITEMS,r4 ; r4 keeps the count of the unsorted numbers
        move    #ARRAY,r2   ; x:(r2) is the first unsorted numbers
        move    #-2,n1      ; used to "back-step" memory pointer 
 
        do      #N_ITEMS-1,_loop2   ; linear scan through the array
        lua     (r2)+,r0    ; Loads the effecive address of (r2)+ to r0
                            ;  This basically loads an incremented r2 to 
                            ;  but r2 remains unchanged
        move    x:(r2),a        y:(r4)-,b 
                            ; This is an example of a parrallel move
                            ;  First we move the first unsorted numbers
                            ;  to a. The second move is actually a trick, we
                            ;  really don't care what is moved to b, but we 
                            ;  just use the auto decrement feature to decrement
                            ;  r4 (that keeps count of the unsorted numbers)
        move    x:(r0)+,b   ; Loads the next unsorted number to b
        move    r0,r1       ; remember that a came from X:(r1-2)
 
        do      r4,_loop1   ; scan through the numbers that are not yet sorted
        cmp     b,a     x:(r0)+,b       b,y0 
                            ; We do a comparison whose results will be used
                            ;  in the next instruction. We also update b
                            ;  with the next value from the array. But since
                            ;  we might need the old value in b, we save it
                            ;  temporarily in y0
        tgt     y0,a    r0,r1 
                            ; If a is greater than b then we have found
                            ;  a smaller number. We save this smaller number 
                            ;  in a and remember where it came from in r1. So
                            ;  the smallest number is always in a and it
                            ;  came from X:(r1-2). Notice that r0 is
                            ;  already auto-incremented, and it takes
                            ;  one loop for the comparison, that is why
                            ;  r1 has to be "back-stepped" two locations.
_loop1 
        move    x:(r2),y0   ; This section of code swaps the smallest value
        move    a,x:(r2)+   ;  with the current value
        move    y0,x:(r1+n1) 
_loop2 
 
loop    jmp     loop 
        end