alg1.asm

; Find Nth algorithm
;
; This algorithm finds the nth largest element in a list. First, it sorts
; the list in descending order and then places the value at index n in
; location 127.
;
; Dynamic Instruction Count for 19.b. at location 30
; 18,240 instructions
; 30th largest element in given array is 32
;
; Registers
; Window A:
; %a0: 62, length of array - 2, temp
; %a1: Iterator for L1, iterates upto n
; %a2: n, we want the nth largest element
; %a3: List[List.length - 2] = Mem[190]
;
; Window B:
; %b0: temp
; %b1: Last index sorted
; %b2: L2 iterator
; %b3: temp
main:
	seti 	4 			; set %a0 to 16

	sli     %a0 2     	; %a0 = 16 * 4. Length of array

	subi    %a0 2       ; Since we begin at location n - 2 of our

; loop

	sub 	%a1 %a1 	; %a1 = 0, L1 iterator

	swapw      			; toggle to window B

	seti    4		    ; set %b0 to 16

	sl      %b0 3       ; set %b0 to 128

	sub     %b0 2       ; set %b0 to 126, location of n

	ld      %b3 %b0 	; loads n from location 126

	movout  %b0 %a2     ; %b0 to %a2

	seti    6           ; set b0 to 24

	sll     %b0 3       ; set b0 to 192

	subi    %b0 2       ; Set to 190, list[list.length - 2].

	movout  %a3 %b0     ; Store array addres in window A.

	sub     %b3 %b3     ; b3 ends up being the last index to be
						; sorted so that we will not sort past that index
						; in our next iteration of L2

	swapw               ; toggle to window A


; Loops at most n times, if the first `n` elements of the list are sorted,
; then the loop halts
L1:

	setlt 	%a1 %a2     ; assert %a1 < %a3 (Loop at most n times)

	bne     ExitL1      ; leave loop when i >= n

	swapw               ; toggle to register window B

	movin    %a2 %b0    ; Temporary hold of n. If elements

; upto n  are sorted, we're done

	sub      %b1 %b1    ; Track the last element sorted, 
						; won't sort passed b1 again, init at 0

	seteq   %b0 %b1     ; assert n == %b1

swapw                   ; always leave in window A

	be      ExitL1      ; Leave loop is b1 == n,

; array is sorted upto n


; Loops from 64 upto last sorted element of the array,
; swapping elements in descending order

	swapw               ; Toggle window B.

	movin	%b2 %a3    	; Bring |list| - 2 (Mem[190]) to current window. 
						; This will be our iterator.

L2:
    setlt   %b2 %b1     ; Assert last sorted element
						; (%b2) > current index.
								
    be 	    ExitL2      ; Exit L2 if %b2 < %b1

    ld      %b3 %b2     ; %b1 = list(%b0)

    subi    %b2 -1      ; move up index
    ld      %b0 %b2     ; b2 = list[iter + 1]

; If List[i + 1] < List[i] then swap.

    setlt   %b0 %b3     ; assert %b0 < %b3 (Descending order)
    bne     Always      ; leave if statement, %b0 >= %b3

    st      %b3 %b2     ; moves b3 to where b0 was in array
    subi    %b0 1       ; decrement pointer
    st      %b0 %b2     ; moves b0 where b1 was in array

    movout  %a0 %b0
    movin     %b1 %a0   ; Save last sorted index

Always:
    subi    %b2 -1      ; Decrement L2 iter.

    seteq   %b0 %b0
    be      L2          ; Branch always.

ExitL2:
    swapw       	    ; Toggle window A
    subi    %a1 -1      ; Inc L1 iter
    seteq   %a0 %a0
    be      L1          ; Branch always to L2

; Array is now sorted up to index n. We now store Array[n] to
; Mem[127]
ExitL1:
    swapw               ; Toggle to window A
    ld   %a0 %a1        ; load value from list at location n

    seti    %a1 4      	; set a1 to 16
    sri     %a1 2
    sri     %a1 1    	; set a1 to 128
    subi    %a1 1       ; set a1 to 127, location for result

    st      %a0 %a1     ; store a0 into Mem[127]

    halt                ; DONE