CS470 Spring 2008

Lab Assignment 3

Due March 14, 11 PM

Updated March 12, 2008

Write a bubble sort program for MIPS assembly language with these specifications:

1. It sorts n 32-bit numbers in memory starting from location ARRAY in ascending order. The number n is given at location NUM.
2. It should include a subroutine INNER with parameter j that does the following (described here in C-like pseudocode):
   
   for(int i=0; i < j; i++){
       if(arr[i] > arr[i+1]){
           temp=arr[i];
           arr[i]=arr[i+1];
           arr[i+1]=temp;
       }
   }
    
3. The main program should called the subroutine enough times:
   
   public void bubbleSort(){
       int temp;
       for(int j=size-1; j > 0; j--){
       INNER(j);
       }
   }
   
    
4. It should work with any set of n numbers, with n equal to 2 or more. Include this array in your program using .word directive.
   
   6, 4, -2, 8, 8, 94, 0, -2
   
    
5. Print the array before and after sorting on the console. When your program is done, it should print a message "Done" on the console.
    

You don't have to use the stack-frames for this assignment. Pass the parameter j using register $a0.

Name the file initial_lastname_l3.asm and submit using RAMCT. Test the program thoroughly before submitting, by trying different arrays. You program should be complete and ready to load in the SPIM simulator. Include appropriate comments. Add your name and S ID at the top.

Note: Since this is your first MIPS assembly language program, you may encounter some questions. Let us discuss these questions in the class on Tuesday.

If your simulator setting uses delayed branches, you may need to have a nop instruction after jr $ra for correct operation.

To see bubble-sort in animation see http://www.ee.unb.ca/petersen/lib/java/bubblesort/  or http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html