MIPS Assembly Language Programming in MARS$/$QtSPIM Simulator: Bubble

Sorting and Finding Average of Array of Numbers

In this project, you will perform sorting of an integer array using recursive techniques in MIPS

assembly language. Sorting is the process of arranging data in an ascending or descending order.

There are many sorting algorithms available. Among them, the Bubble Sort algorithm for sorting

integer data in an array is explained as below. Consider for example the following array containing

integer values. Assume the numbers are unsigned positive integers.

The sort is carried out in two loops. The inner loop passes once through the data comparing

elements in the array and swapping them if they are not in the correct order. For example, element $0$

$(55)$ is compared to element $1(27),$ and they are swapped since $55>27.$

Next element $1($now $55)$ is compared with element $2(13),$ and they are swapped since $55>13.$

This process continues until a complete pass has been made through the array. At the end of the

inner loop the largest value of the array is at the end of the array, and in its correct position. The

array would look as follows.

An outer loop now runs which repeats the inner loop, and the second largest value moves to the

correct position, as shown below.

Repeating this outer loop for all elements results in the array being sorted in ascending order. The

pseudo code for this algorithm is listed as below.

for $($int i $=0$; i $$ size$-1$; i$++)\{$

for $($int j $=0$; j $<mtext\; id="EditorElement\_3699083"></mtext><mi\; id="EditorElement\_3699084">(</mi><mi\; id="EditorElement\_3699085">(</mi>$size$-1)-$i$)$; j$++)\{$

if $($data$[$j$]>$ data$[$j$+1])\{$

swap$($data$,$ j$,$ j$+1)\}$

$\}\}$

swap$($data$,$ i$,$ j$)$

int tmp $=$ data$[$i$]$; data$[$i$]=$ data$[$j$]$; data$[$j$]=$ tmp;

$\}$

Furthermore, the average of N numbers in an array can be calculated as:

Avg $=($N$1+$ N$2+$ N$3+...+$NN$)/$N

Part A: Write MIPS assembly language program to sort $($in ascending order$)$ an array of N unsigned

integer numbers stored in consecutive memory address using the bubble sorting algorithm.

Furthermore, find the average of the N unsigned integer numbers in the array $($assume the average

is rounded up into integer value$).$ Print out the array of numbers before and after sorting. Also print

the average of the array you find $($Avg$=?).$ You can assume any memory address to store your array

of numbers. In your report, clearly explain where your array of numbers before and after sorting are

stored, and how the average of the array is calculated. Define a constant N in your code and use

nested loop structure so that it can handle any number of data to be sorted. Add appropriate

comments to the codes so that they are easily understandable. Print out your assembly program and

attach it with your report.

Part B: Use MARS $($MIPS Assembler and Runtime Simulator$)$ or QtSPIIM $($you can use any of

them$)$ to verify the correctness of your MIPS assembly language program. Capture the screen shot

of your program compilation result to show that your program has been compiled without error.

Then initialize the memory with following example numbers, use $$single$-$step$$ to trace the

execution of your assembly language program step by step. Capture the screen shots of MARS $($or

QtSPIM$)$ execution to shown that you have the array of numbers correctly sorted in memory. Use

hand calculation to find the average of the array. Show your hand calculation in details. Print out

the screenshot of the average you find with the program, and compare it with your hand calculation

result. Are they in good agreement with each other

Part C: Prepare a detailed report for your project. It should include a cover page, introduction,

printout of your program $($list your MIPS assembly language code with explanations in your report$),$

the array of numbers you used to verify the program, captured screen shots of MARS $($or QtSPIM$)$

and explanation$/$analysis for each screen shot, andTable $1.$ Verification of MIPS Assembly Language Program for Sorting and Finding Average of

Array