This assignment is to write a “bubble sort”program in MIPS assembler. Bubble sor
ID: 3616355 • Letter: T
Question
This assignment is to write a “bubble sort”program in MIPS assembler. Bubble sort is one of the simpler sorting algorithms. It gets its name fromthe way smaller elements “bubble” to the top (i.e.,the beginning) of thelist (i.e., linear array) via swaps. The basic idea is to put adjacent elements in the array in sort order;look at the first two elements, swap them if necessary, then look at the second and thirdelements, swap if necessary, then look at the third the fourth elements, swap if necessary,etc. After one pass through the array, the largest item will be at the end of the array.After the second pass through the array, the second largest item will be inposition. After (n-1) such passes, all of the array will be sorted from smallest at thebeginning of the array to largest at the end. for i = 1 to n-1 for j = 0 to n-i-1 if A[j] > A[j+1] swap A[j] and A[j+1] where n is the number of elements in array A. The inner forloop (using j as the loop variable) walks through the array looking at sequentialentries and swapping them if they are out of sort order. The largest element will end up inthe last space that this inner loop examines. The outer loop ensures the inner loopruns (n-1) times. The first time, the largest number will be correctly positioned; thesecond time the next largest number will be correctly positioned and so on until thesmallest number is correctly positioned. Requirements: 1. Your program should prompt the user to enter the positiveinteger (decimal) numbers to be sorted. (1 point) 2. Entering -1 should signal end of input.(1 point) 3. Print array through every pass of the outer loop of thesort, i.e., each time after walking through the array, the intermediate result (apartially sorted list) should be printed.(5 points) 4. Output the sorted array of numbers.(2 points) 4. Comment your program to earn partial credit in case yourprogram doesn’t work.(1 point) 5. Your program will be tested in SPIM, so make sure it worksin SPIM. This assignment is to write a “bubble sort”program in MIPS assembler. Bubble sort is one of the simpler sorting algorithms. It gets its name fromthe way smaller elements “bubble” to the top (i.e.,the beginning) of thelist (i.e., linear array) via swaps. The basic idea is to put adjacent elements in the array in sort order;look at the first two elements, swap them if necessary, then look at the second and thirdelements, swap if necessary, then look at the third the fourth elements, swap if necessary,etc. After one pass through the array, the largest item will be at the end of the array.After the second pass through the array, the second largest item will be inposition. After (n-1) such passes, all of the array will be sorted from smallest at thebeginning of the array to largest at the end. for i = 1 to n-1 for j = 0 to n-i-1 if A[j] > A[j+1] swap A[j] and A[j+1] where n is the number of elements in array A. The inner forloop (using j as the loop variable) walks through the array looking at sequentialentries and swapping them if they are out of sort order. The largest element will end up inthe last space that this inner loop examines. The outer loop ensures the inner loopruns (n-1) times. The first time, the largest number will be correctly positioned; thesecond time the next largest number will be correctly positioned and so on until thesmallest number is correctly positioned. Requirements: 1. Your program should prompt the user to enter the positiveinteger (decimal) numbers to be sorted. (1 point) 2. Entering -1 should signal end of input.(1 point) 3. Print array through every pass of the outer loop of thesort, i.e., each time after walking through the array, the intermediate result (apartially sorted list) should be printed.(5 points) 4. Output the sorted array of numbers.(2 points) 4. Comment your program to earn partial credit in case yourprogram doesn’t work.(1 point) 5. Your program will be tested in SPIM, so make sure it worksin SPIM.Explanation / Answer
.text
.globl _ _start
_ _start:
li $a0,10 #parameter n
sll $a0,$a0, 2 # number of bytes in array A
outer:
sub $t0, $a0, 8 # $t0: j-1
li $t1,0 # no swap yet
inner:
lw $t2,A+4($t0) #$t2 <- A[j]
lw $t3,A($t0) #$t3 <- A[j-1]
bgt $t2, $t3,no_swap # A[j] <= A[j-1]?
sw $t2, A($t0) #A[j-1] <- $t2
movebubble
sw $t3, A+4($t0) # A[j]<- $t3 / $t2
upwards
li $t1,1 #swap occurred
no_swap:
sub $t0, $t0, 4 #next array element
bgez $t0, inner #more?
bnez $t1, outer #did we swap?
li $v0,10 #exit
syscall
.data
A: #array A (sorted in-place)
.word 4,5,6,7,8,9,10,2,1,3