Construct the recursive bubble sort using MIPS. First convert the for loop to a
ID: 3806408 • Letter: C
Question
Construct the recursive bubble sort using MIPS. First convert the for loop to a while loop. Only modify the parts that say "put code here"
void bubbleSort(int arr[], int n)
{
// An array of 1 element is already sorted
if (n == 1) return;
// Put the last element in the right spot
for (int j=0; j<n-1; j++)
if (arr[j] > arr[j+1]) {
int tmp = arr[j]; // Again, swap arr[j] and arr[j+1]
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
// Sort the first n-1 elements
bubbleSort(arr, n-1);
}
Here is what i have so far:
.data
nums: .word 0 : 12 # "array" of 12 words to contain values
size: .word 12 # size of "array"
.text
la $s0, nums
la $s5, size # load address of size variable
lw $s5, 0($s5) # load value of size
# Populate with twelve values
addi $t1, $zero, 55
sw $t1, 0($s0)
addi $t1, $zero, 88
sw $t1, 4($s0)
addi $t1, $zero, 0
sw $t1, 8($s0)
addi $t1, $zero, 22
sw $t1, 12($s0)
addi $t1, $zero, 77
sw $t1, 16($s0)
addi $t1, $zero, 44
sw $t1, 20($s0)
addi $t1, $zero, 99
sw $t1, 24($s0)
addi $t1, $zero, 33
sw $t1, 28($s0)
addi $t1, $zero, 110
sw $t1, 32($s0)
addi $t1, $zero, 66
sw $t1, 36($s0)
addi $t1, $zero, 121
sw $t1, 40($s0)
addi $t1, $zero, 11
sw $t1, 44($s0)
##################################################################
# AT THIS POINT: $s0 is the address of the start of the array
# $s5 is the size (= 12)
#################################################################
##################################################################
# PUT CODE HERE FOR CALL
#
##############################
# SAVE $a registers and $ra
##############################
#
##############################
# Change $a registers
##############################
#
##############################
# jal
##############################
#
##############################
# RELOAD $a registers and $ra
##############################
##################################################################
##################################################################
# DO NOT MODIFY
la $a0, nums # first argument for print (array)
add $a1, $s5, $zero # second argument for print (size)
jal print # call print routine.
li $v0, 10 # system call for exit
syscall # we are out of here.
##################################################################
########################################################################
# PUT CODE HERE FOR FUNCTION
bubblesort:
##################################################################
# SAVE S REGISTERS
##################################################################
##################################################################
# IF STATEMENT
#
addi $t1, $zero, 1
bne $a1, $t1, next
############################
# RETURN FROM FUNCTION
############################
##################################################################
##################################################################
# FOR LOOP
##################################################################
add $s1, $0, $0 #int j=0
addi $t3, $a1, -1#n-1
while:
slt $t2, $s1, $t3 #j < n-1
bne $t2, $t1, loop # branch if not equal
add $t5, $s1, $s1
add $t5, $t5, $t5
add $t5, $t5, $a0
lw $t4, 0($t5) #arr[0]
lw $t6, 4($t5) #j+1
slt $t7, $t5, $t6
beq $0, $t7, jump
jump
add $t5, $t5, 1
##################################################################
# RECURSIVE CALL
#
######################################
# SAVE $a registers, $ra
######################################
#
######################################
# CHANGE $a registers
######################################
#
######################################
# jal
######################################
#
######################################
# RELOAD $a registers, $ra
######################################
##################################################################
##################################################################
# RETURN FROM FUNCTION
##################################################################
Explanation / Answer
Answer:
void bubbleSort(int arr[],int n)
{
if(n==0)
return;
int j = 0;
while (j < n-1)
//for(j=0;j<n-1;j++)
{
if(arr[i+1]>arr[i]) {
int j=arr[i+1];
arr[i+1]=arr[i];
arr[i]=j;
}
i++;
}
bubbleSort(n-1);
}
.LFB0:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
subq $32, %rsp
movl %edi, -20(%rbp)
movl $0, -4(%rbp)
jmp .L2
.L3:
movl -4(%rbp), %eax
cltq
leaq 0(,%rax,4), %rdx
leaq b(%rip), %rax
movl (%rdx,%rax), %eax
movl %eax, %esi
leaq .LC0(%rip), %rdi
movl $0, %eax
call printf@PLT
addl $1, -4(%rbp)
.L2:
movl -4(%rbp), %eax
cmpl -20(%rbp), %eax
jl .L3
movl $10, %edi
call putchar@PLT
nop
leave
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE0:
.size print, .-print
.globl rb
.type rb, @function
rb:
.LFB1:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
subq $32, %rsp
movl %edi, -20(%rbp)
cmpl $0, -20(%rbp)
je .L10
movl $0, -8(%rbp)
jmp .L7
.L9:
movl -8(%rbp), %eax
addl $1, %eax
cltq
leaq 0(,%rax,4), %rdx
leaq b(%rip), %rax
movl (%rdx,%rax), %edx
movl -8(%rbp), %eax
cltq
leaq 0(,%rax,4), %rcx
leaq b(%rip), %rax
movl (%rcx,%rax), %eax
cmpl %eax, %edx
jle .L8
movl -8(%rbp), %eax
addl $1, %eax
cltq
leaq 0(,%rax,4), %rdx
leaq b(%rip), %rax
movl (%rdx,%rax), %eax
movl %eax, -4(%rbp)
movl -8(%rbp), %eax
leal 1(%rax), %ecx
movl -8(%rbp), %eax
cltq
leaq 0(,%rax,4), %rdx
leaq b(%rip), %rax
movl (%rdx,%rax), %edx
movslq %ecx, %rax
leaq 0(,%rax,4), %rcx
leaq b(%rip), %rax
movl %edx, (%rcx,%rax)
movl -8(%rbp), %eax
cltq
leaq 0(,%rax,4), %rcx
leaq b(%rip), %rax
movl -4(%rbp), %edx
movl %edx, (%rcx,%rax)
.L8:
addl $1, -8(%rbp)
.L7:
movl -20(%rbp), %eax
subl $1, %eax
cmpl -8(%rbp), %eax
jg .L9
movl -20(%rbp), %eax
subl $1, %eax
movl %eax, %edi
call rb
jmp .L4
.L10:
nop
.L4:
leave
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE1:
.size rb, .-rb
.globl main
.type main, @function
main:
.LFB2:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
movl $8, %edi
call print
movl $8, %edi
call rb
movl $8, %edi
call print
movl $0, %eax
popq %rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.