In: Computer Science
.data A: .space 80 # create integer array with 20 elements ( A[20] ) size_prompt: .asciiz "Enter array size [between 1 and 20]: " array_prompt: .asciiz "A[" sorted_array_prompt: .asciiz "Sorted A[" close_bracket: .asciiz "] = " search_prompt: .asciiz "Enter search value: " not_found: .asciiz " not in sorted A" newline: .asciiz "\n" .text main: # ---------------------------------------------------------------------------------- # Do not modify la $s0, A # store address of array A in $s0 add $s1, $0, $0 # create variable "size" ($s1) and set to 0 add $s2, $0, $0 # create search variable "v" ($s2) and set to 0 add $t0, $0, $0 # create variable "i" ($t0) and set to 0 addi $v0, $0, 4 # system call (4) to print string la $a0, size_prompt # put string memory address in register $a0 syscall # print string addi $v0, $0, 5 # system call (5) to get integer from user and store in register $v0 syscall # get user input for variable "size" add $s1, $0, $v0 # copy to register $s1, b/c we'll reuse $v0 prompt_loop: # ---------------------------------------------------------------------------------- slt $t1, $t0, $s1 # if( i < size ) $t1 = 1 (true), else $t1 = 0 (false) beq $t1, $0, end_prompt_loop sll $t2, $t0, 2 # multiply i * 4 (4-byte word offset) addi $v0, $0, 4 # print "A[" la $a0, array_prompt syscall addi $v0, $0, 1 # print value of i (in base-10) add $a0, $0, $t0 syscall addi $v0, $0, 4 # print "] = " la $a0, close_bracket syscall addi $v0, $0, 5 # get input from user and store in $v0 syscall add $t3, $s0, $t2 # A[i] = address of A + ( i * 4 ) sw $v0, 0($t3) # A[i] = $v0 addi $t0, $t0, 1 # i = i + 1 j prompt_loop # jump to beginning of loop # ---------------------------------------------------------------------------------- end_prompt_loop: addi $v0, $0, 4 # print "Enter search value: " la $a0, search_prompt syscall addi $v0, $0, 5 # system call (5) to get integer from user and store in register $v0 syscall # get user input for variable "v" add $s2, $0, $v0 # copy to register $s2, b/c we'll reuse $v0 # ---------------------------------------------------------------------------------- # TODO: PART 1 # Translate C code into MIPS (bubble sort) # The above code has already created array A and A[0] to A[size-1] have been # entered by the user. After the bubble sort has been completed, the values im # A are sorted in increasing order, i.e. A[0] holds the smallest value and # A[size -1] holds the largest value. # # int t = 0; # # for ( int i=0; i<size-1; i++ ) { # for ( int j=0; j<size-1-i; j++ ) { # if ( A[j] > A[j+1] ) { # t = A[j+1]; # A[j+1] = A[j]; # A[j] = t; # } # } # } # # ---------------------------------------------------------------------------------- # ---------------------------------------------------------------------------------- # TODO: PART 2 # Translate C code into MIPS (binary search) # The array A has already been sorted by your code above int PART 1, where A[0] # holds the smallest value and A[size -1] holds the largest value, and v holds # the search value entered by the user # # int left = 0; # int right = size - 1; # int middle = 0; # int element_index = -1; # # while ( left <= right ) { # # middle = left + (right - left) / 2; # # if ( A[middle] == v) { # element_index = middle; # break; # } # # if ( A[middle] < v ) # left = middle + 1; # else # right = middle - 1; # # } # # if ( element_index < 0 ) # printf( "%d not in sorted A\n", v ); # else # printf( "Sorted A[%d] = %d\n", element_index, v ); # # ---------------------------------------------------------------------------------- # ---------------------------------------------------------------------------------- # Do not modify the exit # ---------------------------------------------------------------------------------- exit: addi $v0, $0, 10 # system call (10) exits the progra syscall # exit the program
Please up vote ,comment if any query . Thanks for Question . Be safe .
Note : check attached image for output .code compiled and tested in MARS MIPS simulator .
Program :
.data
A:
.space
80 # create integer array with
20 elements ( A[20] )
size_prompt:
.asciiz "Enter
array size [between 1 and 20]: "
array_prompt:
.asciiz "A["
sorted_array_prompt:
.asciiz "Sorted
A["
close_bracket:
.asciiz "] =
"
search_prompt:
.asciiz "Enter search value: "
not_found:
.asciiz " not in sorted A"
newline:
.asciiz
"\n"
.text
main:
#
----------------------------------------------------------------------------------
# Do not modify
la $s0,
A
# store address of array A in $s0
add $s1, $0,
$0
# create variable "size" ($s1) and set to 0
add $s2, $0,
$0
# create search variable "v" ($s2) and set to 0
add $t0, $0,
$0
# create variable "i" ($t0) and set to 0
addi $v0, $0,
4
# system call (4) to print string
la $a0,
size_prompt
# put string memory address in register $a0
syscall
# print string
addi $v0, $0,
5
# system call (5) to get integer from user and store in register
$v0
syscall
# get user input for variable "size"
add $s1, $0,
$v0
# copy to register $s1, b/c we'll reuse $v0
prompt_loop:
#
----------------------------------------------------------------------------------
slt $t1, $t0,
$s1
# if( i < size ) $t1 = 1 (true), else $t1 = 0 (false)
beq $t1, $0,
end_prompt_loop
sll $t2, $t0,
2
# multiply i * 4 (4-byte word offset)
addi $v0, $0,
4
# print "A["
la $a0,
array_prompt
syscall
addi $v0, $0,
1
# print value of i (in base-10)
add $a0, $0,
$t0
syscall
addi $v0, $0,
4
# print "] = "
la $a0,
close_bracket
syscall
addi $v0, $0,
5
# get input from user and store in $v0
syscall
add $t3, $s0,
$t2
# A[i] = address of A + ( i * 4 )
sw $v0,
0($t3)
# A[i] = $v0
addi $t0, $t0,
1
# i = i + 1
j
prompt_loop
# jump to beginning of loop
#
----------------------------------------------------------------------------------
end_prompt_loop:
#starting of bubble sort
bubble_sort:
li $t0,0 #loop index i=0
la $s0,A #load address of array in
$s0
firstForLoop: #outer side
loop
bge
$t0,$s1,endOfBubbleSort #if i greater than or equal to size go to
endOfbubblesort label
addi $s3,$s0,0 #load address in $s3 from
$s0
li $t1,0 #loop index j=0 inner loop
addi $t2,$s1,-1 #size -1 in $t2
sub $t2,$t2,$t0 #sub size-1-i
secondForLoop:#inner loop
bge $t1,$t2,secondForLoopEnd #while $t1<$t2
else go to secondLoopEnd
lw $t3,0($s3) #load A[j] into $t3
lw $t4,4($s3) #load A[j+1] into
$t4
#if A[j] <= A[4] go to no need to swap
ble $t3,$t4,skip #else swap
sw $t4,0($s3) #store $t4 at
A[j]
sw $t3,4($s3) #store $t3 at A[j+1]
skip:
addi $t1,$t1,1 #increment j by 1
addi $s3,$s3,4 #point to next element of
Array
j secondForLoop #jump to secondForLoop inner
loop
secondForLoopEnd: #if inner loop completes increment i and jump to
outer loop
addi $t0,$t0,1
j firstForLoop
#end of bubble sort
endOfBubbleSort:
addi $v0, $0,
4
# print "Enter search value: "
la $a0,
search_prompt
syscall
addi $v0, $0,
5
# system call (5) to get integer from user and store in register
$v0
syscall
# get user input for variable "v"
add $s2, $0,
$v0
# copy to register $s2, b/c we'll reuse $v0
#binary search start
from here
binarySearch:
la $s0,A #address of array A in $s0
li $t0,0 #left
addi $t1,$s1,-1 #size-1 into right
li $t2,0 #middle
li $t3,-1 #element index
searchLoop: #loop till left<=right
bgt
$t0,$t1,endOfSearch #if left>right go to endOfSearch
sub $t2,$t1,$t0 #$t2=middle =
right-left
div $t2,$t2,2
#t2=middle =( right-left)/2
add $t2,$t2,$t0 #t2=middle =
left($t0)+ ( right-left)/2
mul $t4,$t2,4
#multiply $t4= $t2*4 to go to element
addres
add $t4,$t4,$s0 #address of current
element A[0] + $t4 = address of middle
lw $t5,0($t4) #A[middle] =
$t5
bne $t5,$s2,skipSearch
#if $t5!=$t4(v) skip search
addi $t3,$t2,0 #else
if equal elementindex = middle= $t3
j endOfSearch #go to endOfSearch element
found
skipSearch: #if not found
blt $t5,$s2,lessValue
#A[middle]<v go to less value
addi $t1,$t2,-1 #if greater
right=middle-1 = $t1=$t2-1
j searchLoop
#jump to search loop
lessValue: #A[middle]<v
addi $t0,$t2,1 #left=middle+1
$t0=$t2+1
j searchLoop #jump to search
loop
endOfSearch:
#if elementIndex<0 element not found go to
notSorted label
blt $t3,0,notSorted #else here
#print sorted A[
la $a0,sorted_array_prompt
li $v0,4
syscall
#print element index
addi $a0,$t3,0
li $v0,1
syscall
#print close bracket
la $a0,close_bracket
li $v0,4
syscall
#print value of v in $s2
addi $a0,$s2,0
li $v0,1
syscall
#print new line
la $a0,newline
li $v0,4
syscall
j exit #jump to exit
notSorted:
#print v
li
$v0,1
addi
$a0,$s2,0
syscall
#print not found string
la
$a0,not_found
li
$v0,4
syscall
#print new line
la
$a0,newline
li
$v0,4
syscall
#terminate program
exit:
li $v0,10
syscall
Output 1 :
Output : 2
Memory Layout :
Please up vote ,comment if any query . Thanks for Question . Be safe .