MIPS Programming Sorting Iteratively and Recursively

CS 270 Fall 2018

Project Available		Oct. 10
Component	Points	Due Date (at 11:59 pm)
Functionality - Iterative	20
Functionality - Recursive	20
Proper Stack Usage	10
Code Translation	10
Style	15
Total	75	Oct. 31
Submission	individual	Autolab

Objectives

The goal of this assignment is to work with functions, recursion, arrays, memory, and pretty printing the array contents. You will achieve this by translating the C code given to you. Be sure to do this how a compiler would as we have discussed in class.

Deliverables

You will write two MIPS programs called simplesort.asm and recsort.asm, and submit them for grading to Autolab. Your Autolab score is only part of your overall grade for the assignment. Take care to follow all of the style guidelines.

Sample Input

7 2 5 1 -7 2 4 16

Sample Output

The elements sorted in ascending order are: -7, 1, 2, 2, 4, 5, 16

CS 270 MIPS Programming Page 2 of 3

1 Simple Sort

Write a MIPS program that uses an implementation of selection sort to sort an array of numbers. The values of the array will be given to you via standard input and separated by newlines. The first number will be the number of elements in the array and followed by the elements of the array in order. You can assume that there will be at least one, and no more than 20 numbers in the array. Each number will fit in a signed 4 byte integer. After sorting the numbers, you should write them to standard out in increasing order. Your code should be able to handle an array with numbers that have the same value. For full credit, your code must be a valid translation of the selection sort implementation on the next page of this document. Your code must include a function that performs the sorting. That function should not call any other functions. The array should be declared in the static data portion of memory.

Selection Sort Implementation - C

void selection sort(int arr[], int len) {

int i, j, tmp, min, Index;

for (i=0; i

minIndex = i ;

for (j=i+1; j

if (arr[minIndex] > arr[j]) {

minIndex = j ;

}

}

if (minIndex != i) {

tmp = arr[minIndex];

arr[minIndex] = arr[i];

arr[i] = tmp; } } }

2 Recursive Sort

Write a MIPS program that uses an implementation of quicksort to sort an array of numbers. The values of the array will be given to you via standard input and separated by newlines. The first number will be the number of elements in the array and followed by the elements of the array in order. You can assume that there will be at least one, and no more than 20 numbers in the array. Each number will fit in a signed 4 byte integer. After sorting the numbers, you should write them to standard out in increasing order. Your code should be able to handle an array with numbers that have the same value. For full credit, your code must be a valid translation of the quicksort implementation on the next page of this document. Your code must adhere to the MIPS style guidelines discussed in class. Your code must include the two functions listed below and handle the stack appropriately for recursive calls.

The input and output format will be the same as the simple sort, so I recommend reusing the code to read in the data, and print the contents of the array.

Quicksort Implementation - C

int partition(int arr [] , int left , int right) {

int i = left, j = right;

int tmp;

int pivot = arr[(left + right) / 2];

while (i <= j) {

while (arr [ i ] < pivot)

i ++;

while (arr [ j ] > pivot)

j ;

if (i <= j) {

tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;i ++;

j ;

}

}

return i ;

}

void quickSort(int arr [] , int left , int right) {

int index = partition(arr, left , right);

if (left < index 1)

quickSort(arr , left , index 1);

if (index < right)

quickSort(arr , index , right );

}