Create MIPS assembly code for the following C function. It is an insertion sort
ID: 3664363 • Letter: C
Question
Create MIPS assembly code for the following C function. It is an insertion sort
program.
You don’t need to generate any code for the include, namespace, and function prototype
lines. Assume the random number function is at memory address RAND :, and
don’t generate code for it.
Remember that any local values in temporary registers will NOT be maintained across function calls. If you use a saved register, you must maintain the original value by placing it on the stack, and then restoring the original value
at the end.
It might be easier to write the shift function first, then write the main
function.
// Don’t generate any MIPS for the next 4 lines
#include
#include
using namespace std;
void shift( int array[], int index );
// start creating MIPS code for the rest.
// Note that some lines are commented (no code for those)
int main(){
int array[1000];
int x;
for( int i = 0; i < 1000; i++ ){
array[i] = 2001;
}
// for ( int i = 0; i < 1000; i++ ) cout << array[i] << " ";
// cout << "----"<
// Assume function rand() is implemented at memory address RAND
// and it returns a random integer in register $v0
for( int i = 0; i < 1000; i++){
x = rand()%2000;
for ( int j = 0;j < 1000; j++ ) {
if ( x < array[j] ){
shift( array, j);
array[j] = x;
j = 1000;
}
}
}
// for ( int i = 0; i < 1000; i++ ) cout << array[i] << " ";
// cout << "----"<
}
void shift( int array[], int index ){
for (int i = 999; i > index; i-- )
array[i] = array[ i-1 ];
}
Explanation / Answer
# first for loop
li $x, 0 #x=0
li $i, 0 #i =0
loop bge $i, $x ,end
array : . space 100
lw $i ,2001
sw $i , 2001 #array[i]=2001
j loop
end:
#2nd for loop
li $x, 0 #x=0
li $i, 0 #i =0
loop bge $i, $x ,end
loop: li $j ,0 #j=0
array : .space 100
lw $j ,0
sw $j 0 #array[j]
bge $x,$j
lw $j ,1000
sw $j ,1000 #j=1000
j loop
end:
array : . space 100
lw $i ,2001
sw $i , 2001 #array[i]=2001
i loop
end:
#3rd for loop
li $index, 0 #index=0
li $i, 999 #i =999
loop bge $i, $index,end
array : . space 100
lw $i ,0
sw $i , $i -1 #array[i]=array[i-1]
i loop
end: