Problems (to be solved on LEGv8 assembly; all code should adhere to standard register, stack use, paremeter passing, etc. conventions, as discussed in lecture and the textbook):

* Implement a swap procedure that swaps the values in two different 8-byte integers in memory. * Implement a find smallest procedure that finds the smallest 8-byte integer in an array and returns its index. * Implement selection sort using your find smallest and swap procedures. To be clear, selection sort can be more efficiently implemented without any helper procedures, but implementing it in assembly is easier with the helpers--and it gives you experience with procedure calls and stack manipulation--so we are requiring that you do it this way.

Pseudocode for the selection sort:

SelectionSort(array) for each element in array in order from first to last: swap element with smallest element in the subarray that it begins

* Implement a procedure to fill an array with consecutive 8-byte integers in reverse-sorted (high to low) order * Implement a "main" procedure that ties all of this together by: ** Calling your fill procedure to create a reverse sorted array in main memory. ** Sorting that array using your selection sort implementation ** Program ends with a DUMP

How to get started:

1) Get an environment running

2) Write all of your algorithms in C, or some similar language. If you do it

in, e.g., Java, keep it C like (use only primitives and arrays). Make

sure your code works. You'll use it to help you reason about your

assembly. In a sense, you'll compile it by hand.

3) Write the array builder first. It will configure your memory in a way

that makes it easy to check that other procedures work.

4) Do swap next. Run your array builder. Then test that you can swap any

arbitrary pair of values in the array.

5) Find smallest is next. If you run it on your whole array, it will always

return the array size - 1 (if you haven't swapped). It should also work

on some arbitrary sub array specified by changing the parameters (hint,

there need to be two of them).

6) Finally do selection sort (you should have been developing "main" all

along to test your other procedures).