Computer Science 220
Assembly Language & Computer Architecture

Fall 2010, Siena College

Home     Syllabus     Schedule

For this lab, you will gain more experience with MIPS programming by implementing an insertion sort for an array of integers. You may work alone or with a partner on this lab.

In Lab: Factorial Program

First, take a look at the complete version of the factorial program described in last week's lab.

See Example:
~jteresco/shared/cs220/examples/spim-factorial/factorial.s

Second, if you are not familiar with/do not recall the details of insertion sort, look it up and remember/learn them.

Programming Tasks

Your MIPS implementation of insertion sort should be based on one of the C functions found in the file

~jteresco/shared/cs220/labs/spim-sort/isort.c

Begin by making sure you understand both versions. Draw some examples. You should have a lot of boxes and arrows.

You should write the insertion sort in a subroutine named isort. It should be called from main, and take two parameters: the address of the start of the array, and the number of integers in the array, passed using the standard MIPS conventions for subroutine calls and register usage. You may base your code on either of the functions in isort.c.

Think carefully about how to approach the compound conditional in the while loop. You may find it helpful to rewrite it first as a series of if statements with gotos.

Set up an array in memory and initialize it with a collection of random values (randomly chosen by you at programming time, not by SPIM at run time).

Your main routine should call a subroutine to print out the initial array (which you will write), call isort, then print the array again through another subroutine call. Label your output appropriately.

In summary, your submission should include three complete MIPS subroutines: main, isort, and the one to print the contents of the array. main calls the print function, then isort, then the print function again.

Submission and Evaluation

This lab is graded out of 30 points.

By 2:30 PM, Tuesday, October 19, 2010, submit a single file called isort.s that includes your documented MIPS assembly source code for your program. Submit by email to jteresco AT siena.edu.

Note: During grading, I will replace your array's contents with my own, so be sure your programs work with a variety of array sizes and contents. Also, make sure that your programs work in SPIM on the CS Linux systems, as that is where I will test your programs.

Pay close attention again to appropriate documentation practices. It is always good to document as you go when doing any kind of programming, but it especially crucial for assembly language programming. And don't forget to include your name!