Lab 4: MIPS Array

Your task is to write a program to read a list of (x,y) pairs representing points in the xy-plane and print them in ascending order, according to their distance from the origin. You will write this program in MIPS using the MARS simulator

Preliminaries

Click on the assignment link.

Once you have accepted the assignment, you can clone the repository on your computer by following the instruction and begin working.

Be sure to ask any questions on Piazza.

Program specification

No starter code is provided this time. Create a file in MARS called lab4.asm and create your program there. You may wish to look at your code for Lab 3 for reference.

Input

The first line of input is an integer $n$ ($1 \leq n \leq 1000$) representing the number of points in the list. $n$ is followed by $2n$ additional lines of input containing the coordinates of the points to be sorted. For example, the list $\{ (3,4), (4,2), (0,-5), (1,3) \}$ would be input as:

4
3
4
4
2
0
-5
1
3

You can read the values using system call 5 (read integer). (System call 5 requires that only one integer appear on each line.)

The input should be stored in an array. You can view the storage conceptually as a series of pairs, as shown below.

3  4
4  2
0 -5
1  3

Output

The output of the program will consist of $n$ lines, each containing the x- and y-coordinates of one point in the sorted list. For example, the output from the list of 4 points shown above would be the following.

1    3
4    2
0    -5
3    4

Implementation

You will need to

• allocate space for the data;
• decide how to map the data to the space you allocate; and
• determine how to address the x- and y-coordinates of each point.

Once you have read in all the data, you need to sort it in increasing order according to the value of $x^2 + y^2$; that is, the square of the distance from the point to the origin. If two points in your list are the same distance from the origin, they should be sorted in lexicographic order; that is, first in increasing order according to the x-coordinate, and if the x-coordinates are the same, then according to the y-coordinate. If the same point appears more than once in the input, it should appear with the same multiplicity in the output. For example, the correct ordering of the points $(0,-5)$, $(3,4)$, $(4,-3)$, $(-3,4)$, $(-5,0)$ would be $(-5,0)$, $(-3,4)$, $(0,-5)$, $(3,4)$, $(4,-3)$.

You may use any sort method that you choose. I would recommend using something simple like insertion sort. Keep in mind that when you swap two points in your list, you must swap both their x- and y-coordinates.

You may assume that overflow will not occur as a result of computing $x^2 + y^2$.

Suggested plan for developing the program

First, write and debug a program that will read $n$ and the list of points, store each point in the array, and print it in the desired format.

After that, go back and add the sort operation. Make sure to test!

Helpful resources

• A guide to the MARS simulator
• A list of MIPS system calls

Submission

Submit the lab by committing your code and pushing it to your GitHub repository.