For this project, i am tasked with switching an array from depth first sort into breadth first and vice versa in mars4_5, I had already did the depth first to breadth first as below.
.data
# Initial array in breadth-first order
breadth_array: .word 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
# Space for depth-first array
depth_array: .space 60 # 15 elements * 4 bytes
# String for printing output
newline: .asciiz "n"
msg: .asciiz "Depth-first array: "
.text
.globl main
main:
# Initialize the base addresses
la $a0, breadth_array # $a0 = base address of breadth_array
la $a1, depth_array # $a1 = base address of depth_array
# Initialize indices for traversal
li $a2, 0 # $a2 = breadth_array index
li $a3, 0 # $a3 = depth_array index
# Call the recursive function
jal pre_order # Jump to pre_order
# Print the message
li $v0, 4 # syscall to print string
la $a0, msg # load address of message
syscall
# Print the depth-first array
la $t1, depth_array # Load the base address of the depth-first array
li $t3, 15 # Number of elements in the array
li $t4, 0 # Index to traverse the array
print_loop:
beq $t4, $t3, exit # If index == number of elements, exit loop
lw $a0, 0($t1) # Load the current element of depth_array into $a0
li $v0, 1 # syscall to print integer
syscall
# Print newline after each number
li $v0, 4 # syscall to print string
la $a0, newline # load address of newline
syscall
addi $t1, $t1, 4 # Move to the next element
addi $t4, $t4, 1 # Increment index
j print_loop # Repeat the loop
exit:
li $v0, 10 # Exit program
syscall
# Recursive pre-order traversal function
# Arguments:
# $a0 = breadth_array base address
# $a1 = depth_array base address
# $a2 = breadth_array index
# $a3 = depth_array index (passed by value, needs to be returned)
pre_order:
addi $sp, $sp, -16 # Allocate stack space
sw $ra, 12($sp) # Save return address
sw $s0, 8($sp) # Save $s0 (depth_array base address)
sw $s1, 4($sp) # Save $s1 (breadth_array index)
sw $s2, 0($sp) # Save $s2 (depth_array index)
move $s0, $a1 # $s0 = depth_array base address
move $s1, $a2 # $s1 = breadth_array index
move $s2, $a3 # $s2 = depth_array index
sll $t0, $s1, 2 # $t0 = $s1 * 4 (word offset)
add $t0, $t0, $a0 # $t0 = address of breadth_array[$s1]
lw $t5, 0($t0) # Load breadth_array[$s1]
sll $t1, $s2, 2 # $t1 = $s2 * 4 (word offset)
add $t1, $t1, $s0 # $t1 = address of depth_array[$s2]
sw $t5, 0($t1) # Store in depth_array[$s2]
addi $s2, $s2, 1 # Increment depth_array index
# Calculate left child index (2*i + 1)
sll $t6, $s1, 1
addi $t6, $t6, 1
blt $t6, 15, call_left # Check if left child index is within bounds
j skip_left
call_left:
move $a2, $t6
move $a3, $s2
jal pre_order
move $s2, $v0 # Update depth_array index from return value
skip_left:
# Calculate right child index (2*i + 2)
sll $t7, $s1, 1
addi $t7, $t7, 2
blt $t7, 15, call_right # Check if right child index is within bounds
j skip_right
call_right:
move $a2, $t7
move $a3, $s2
jal pre_order
move $s2, $v0 # Update depth_array index from return value
skip_right:
move $v0, $s2 # Return updated depth_array index
lw $ra, 12($sp) # Restore return address
lw $s0, 8($sp) # Restore $s0
lw $s1, 4($sp) # Restore $s1
lw $s2, 0($sp) # Restore $s2
addi $sp, $sp, 16 # Deallocate stack space
jr $ra # Return from function
with the result 1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15
and now i need to reverse it to work from depth first into breadth first and what i have reached is
.data
# Initial array in depth-first order (pre-order traversal)
depth_array: .word 1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15
# Space for breadth-first array
breadth_array: .space 60 # 15 elements * 4 bytes
# String for printing output
newline: .asciiz "n"
msg: .asciiz "Breadth-first array: "
.text
.globl main
main:
# Initialize the base addresses
la $a0, depth_array # $a0 = base address of depth_array
la $a1, breadth_array # $a1 = base address of breadth_array
# Initialize indices for traversal
li $a2, 0 # $a2 = depth_array index
li $a3, 0 # $a3 = breadth_array index
li $t5, 0 # $t5 = level (initially root level)
# Call the recursive function
jal breadth_order # Jump to breadth_order
# Print the message
li $v0, 4 # syscall to print string
la $a0, msg # load address of message
syscall
# Print the breadth-first array
la $t1, breadth_array # Load the base address of the breadth-first array
li $t3, 15 # Number of elements in the array
li $t4, 0 # Index to traverse the array
print_loop:
beq $t4, $t3, exit # If index == number of elements, exit loop
lw $a0, 0($t1) # Load the current element of breadth_array into $a0
li $v0, 1 # syscall to print integer
syscall
# Print newline after each number
li $v0, 4 # syscall to print string
la $a0, newline # load address of newline
syscall
addi $t1, $t1, 4 # Move to the next element
addi $t4, $t4, 1 # Increment index
j print_loop # Repeat the loop
exit:
li $v0, 10 # Exit program
syscall
# Recursive breadth-order traversal function
# Arguments:
# $a0 = depth_array base address
# $a1 = breadth_array base address
# $a2 = depth_array index
# $a3 = breadth_array index
# $t5 = current level
breadth_order:
addi $sp, $sp, -20 # Allocate stack space
sw $ra, 16($sp) # Save return address
sw $s0, 12($sp) # Save $s0 (breadth_array base address)
sw $s1, 8($sp) # Save $s1 (depth_array index)
sw $s2, 4($sp) # Save $s2 (breadth_array index)
sw $s3, 0($sp) # Save $s3 (current level)
move $s0, $a1 # $s0 = breadth_array base address
move $s1, $a2 # $s1 = depth_array index
move $s2, $a3 # $s2 = breadth_array index
move $s3, $t5 # $s3 = current level
# Load depth_array[$s1] and store in breadth_array[$s2]
sll $t0, $s1, 2 # $t0 = $s1 * 4 (word offset)
add $t0, $t0, $a0 # $t0 = address of depth_array[$s1]
lw $t6, 0($t0) # Load depth_array[$s1]
sll $t1, $s2, 2 # $t1 = $s2 * 4 (word offset)
add $t1, $t1, $s0 # $t1 = address of breadth_array[$s2]
sw $t6, 0($t1) # Store in breadth_array[$s2]
addi $s2, $s2, 1 # Increment breadth_array index
# Calculate left and right child indices in depth_array
addi $t7, $s1, 1 # $t7 = left child index
sll $t7, $t7, 1 # $t7 = 2 * left child index (left and right children)
add $t8, $t7, 0 # $t8 = right child index
# Check if left child index is within bounds
blt $t7, 15, call_left
skip_left:
# Check if right child index is within bounds
blt $t8, 15, call_right
skip_right:
move $v0, $s2 # Return updated breadth_array index
lw $ra, 16($sp) # Restore return address
lw $s0, 12($sp) # Restore $s0
lw $s1, 8($sp) # Restore $s1
lw $s2, 4($sp) # Restore $s2
lw $s3, 0($sp) # Restore $s3
addi $sp, $sp, 20 # Deallocate stack space
jr $ra # Return from function
call_left:
move $a2, $t7
move $a3, $s2
addi $t5, $s3, 1 # Increment level
jal breadth_order
move $s2, $v0 # Update breadth_array index from return value
j skip_left
call_right:
move $a2, $t8
move $a3, $s2
addi $t5, $s3, 1 # Increment level
jal breadth_order
move $s2, $v0 # Update breadth_array index from return value
j skip_right
but this just outputs the same depth first order.
I tried sorting the depth first array into breadth first, but the output is still depth first sort