Question

In: Computer Science

.data A: .space 80 # create integer array with 20 elements ( A[20] ) size_prompt: .asciiz...

.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
  

Solutions

Expert Solution

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 .


Related Solutions

Please Solve with c language Create 5-by-5 integer array. Initialize the elements of the array starting...
Please Solve with c language Create 5-by-5 integer array. Initialize the elements of the array starting from 1. Your element [0][0] should be equal to 1; element[4][4] should be equal 25. Print the array. The output should have 5 rows and 5 columns. Specify the width for each output to demonstrate the table in a formatted view. Change the value of the elements: 2nd row 4th column to 24, 1st row 3rd column to 13. Print the array again. Find...
This assignment asks to create an array with 10 integer elements. Ask user to input 10...
This assignment asks to create an array with 10 integer elements. Ask user to input 10 integer values. going through all the array elements and find/print out all the prime numbers. Instructions: Only use for loops for this lab (no need to create methods or classes for this assignment). Put a comment on each line of your codes, explaining what each line of code does. basic java, please
How to create a two-dimensional array, initializing elements in the array and access an element in...
How to create a two-dimensional array, initializing elements in the array and access an element in the array using PHP, C# and Python? Provide code examples for each of these programming languages. [10pt] PHP C# Python Create a two-dimensional array Initializing elements in the array Access an element in the array
Write a C function to swap the first and last elements of an integer array. Call...
Write a C function to swap the first and last elements of an integer array. Call the function from main() with an int array of size 4. Print the results before and after swap (print all elements of the array in one line). The signature of the arrItemSwap() function is: void arrItemSwap(int *, int, int); /* array ptr, indices i, j to be swapped */ Submit the .c file. No marks will be given if your pgm does not compile...
Write code that would allocate the space for an array of 20 integers. It will be...
Write code that would allocate the space for an array of 20 integers. It will be pointed to by a variable named "junk" Write code that puts “file did not open” into an error stream.
Write a c program Write a function to swap two elements of an integer array. Call...
Write a c program Write a function to swap two elements of an integer array. Call the function to swap the first element, i[0] with last element i[n], second element i[1] with the last but one element i[n-1] and so on. Should handle arrays with even and odd number of elements. Call the swap function with the following arrays and print results in each case before and after swapping. i. int arr1[] = {0, 1, 2, 3, 30, 20, 10,...
C++ Program 1. Declare an integer static array a[ ] with 100 elements. 2. Declare an...
C++ Program 1. Declare an integer static array a[ ] with 100 elements. 2. Declare an integer pointer p. 3. Let p pointing to the array a[ ]. 4. Use p (you have to use p) to put 0 into the first element of this array, 2 into the second element, 4 into the 3rd element, 6 into the 4th element, ... 198 into the 100th element of this array. 5. Use a (you have to use a) to display...
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array...
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time. Return that integer. Input: arr = [1,2,2,6,6,6,6,7,10] Output:
Write a c program arrays2.c that checks if an integer array contains three identical consecutive elements....
Write a c program arrays2.c that checks if an integer array contains three identical consecutive elements. Assume the number of identical consecutive elements are no more than three if they exist. Sample input/output #1: Enter the length of the array: 11 Enter the elements of the array: -12 0 4 2 2 2 36 7 7 7 43 Output: The array contains 2 of three identical consecutive elements: 2 7 Sample input/output #2: Enter the length of the array: 4...
Write a Pseudo Code to send an Array of 20 elements from 8051 to the computer...
Write a Pseudo Code to send an Array of 20 elements from 8051 to the computer via serial port at maximum baud rate possible with XTAL=11.0592MHz.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT