Ik probeer een procedure in assembly te schrijven die een array sorteert met behulp van het bubble-sort-algoritme, maar ik heb een probleem dat is:
In line 22, wanneer de eerste iteratie is uitgevoerd, is er niets mis, het programma laadt array[i+1] perfect in registrar $a1 en als de swap-voorwaarde geldig is, kunt u zonder problemen wisselen van programma’s. In de tweede iteratie laadt het programma echter altijd 0 in $a1, ongeacht de werkelijke waarde van het element! Ik heb geprobeerd het te debuggen, maar niets was duidelijk en ik weet niet wat de oorzaak hiervan is.
1. # Procedure: bubbleSort
2. # Objective: sort an array of integer elements in nondecreasing order
3. # Input: an address of an array of integers
4. # Output: an array sorted in nondecreasing order
5.
6. bubbleSort:
7.
8. move $t0, $a0 # move address of the array into $t0
9. li $s0, 1 # boolean swap = false. 0 --> false, 1 --> true
10. li $t1, 0 # j = 0;
11. li $t2, 0 # i = 0;
12. li $s1, 9 # array length
13. loop:
14. beqz $s0, exit # exit if swap = false
15. li $s0, 0 # swap = false;
16. addiu $t1, $t1, 1 # j++;
17. move $t2, $0 # i = 0;
18. subu $s2, $s1, $t1 # s2 = length - j
19. forLoop:
20. bge $t2, $s2, exitForLoop # if i>=s2, exit
21. lw $a0, 0($t0) # a0 = array[i]
22. lw $a1, 4($t0) # a1 = array[i+1]
23. ble $a0, $a1, update # if array[i]<=array[i+1] skip
24. sw $a1, 0($t0) # a[i+1] = a[i]
25. sw $a0, 4($t0) # a[i] = a[i+1]
26. li $s0, 1 # swap = true;
27. update:
28. addiu $t2, $t2, 1 # i++
29. sll $t3, $t2, 2 # t3 = i*4
30. addu $t0, $t0, $t3 # point to next element -->
31. j forLoop
32. exitForLoop:
33. j loop
34. exit:
35. jr $ra
Antwoord 1, autoriteit 100%
Ik heb net een opdracht afgerond met hetzelfde doel; een bubbelsortering uitvoeren op gebruikersinvoer met de veronderstelling dat de gebruikersinvoer een reeks van tien tekens is die letters zijn. Ik heb er commentaar op gegeven, dus voel je vrij om het als referentie te gebruiken. De opdracht is nog niet beoordeeld, ik hoop alleen dat ze niet denken dat ik vals speel omdat ze dit op internet hebben gevonden.
####################################################################################################################################
# Data
####################################################################################################################################
.data
prompt: .asciiz "\n\nEnter up to 10 characters: " # Prompt asking for user input
newLine: .asciiz "\n" # Newline character
theString: .asciiz " " # A ten character string initially filled with whitespace
####################################################################################################################################
# Text
####################################################################################################################################
.text
################################################################################################################
##### Procedure: Main
##### Info: Asks user for input, gets input, and then call
##### procedures to manipulate the input and output.
################################################################################################################
main:
############################################################
# Print Prompt
############################################################
la $a0, prompt # Load address of prompt from memory into $a0
li $v0, 4 # Load Opcode: 4 (print string)
syscall # Init syscall
#############################################
# Read User Input into address of theString
#############################################
la $a0,theString # Load address of theString into syscall argument a0
li $a1,11 # Load sizeOfInput+1 into syscall argument a1
li $v0,8 # Load Opcode: 8 (Read String)
syscall
##############################
# Define total num of chars
##############################
li $s7,10 # s7 upper index
##############################
# Call procedures
##############################
jal uppercase
jal sort
jal print
j exit
################################################################################################################
############################################# main END #######################################################
################################################################################################################
################################################################################################################
##### Procedure: uppercase
##### Info: Loops through the ten elements of chars gathered from
##### user input and if ascii is in range between 97
##### and 122, it will subtract 32 and store back
################################################################################################################
uppercase:
la $s0, theString # Load base address to theString into $t0
add $t6,$zero,$zero # Set index i = 0 ($t6)
lupper:
#####################################
# Check for sentinal val and if true
# branch to done to jump back to ra
#####################################
beq $t6,$s7,done
#####################################
# Load Array[i]
#####################################
add $s2,$s0,$t6 #
lb $t1,0($s2)
#####################################
# if char is within lowercase
# range.
#####################################
sgt $t2,$t1,96
slti $t3,$t1,123
and $t3,$t2,$t3
#####################################
# else, don't store byte
#####################################
beq $t3,$zero,isUpper
addi $t1,$t1,-32
sb $t1, 0($s2)
isUpper:
#####################################
# increment and Jump back
#####################################
addi $t6,$t6,1
j lupper
################################################################################################################
############################################# uppercase END ##################################################
################################################################################################################
################################################################################################################
##### Procedure: sort
##### Info: Bubble sorts whatever is contained within
##### theString based on ascii values
################################################################################################################
sort:
####################################
# Initialize incrementer for outer
# loop
####################################
add $t0,$zero,$zero
####################################
# Outer Loop
####################################
loop:
#####################################
# Check for sentinal val and if true
# branch to done
#####################################
beq $t0,$s7,done
####################################
# Initialize upper bound of inner
# loop ( 10 - i - 1 )
####################################
sub $t7,$s7,$t0
addi $t7,$t7,-1
####################################
# Initialize incrementer for inner
# loop
####################################
add $t1,$zero,$zero
####################################
# Inner Loop
####################################
jLoop:
#####################################
# Check for sentinal val and if true
# branch to continue
#####################################
beq $t1,$t7,continue
####################################
# Load Array[i] and Array[i+1]
####################################
add $t6,$s0,$t1
lb $s1,0($t6)
lb $s2,1($t6)
#########################################
# If ascii(Array[i]) > ascii(Array[i+1])
# then swap and store
#########################################
sgt $t2, $s1,$s2
#########################################
# Else, don't swap and store
#########################################
beq $t2, $zero, good
sb $s2,0($t6)
sb $s1,1($t6)
good:
#########################################
# increment and Jump back
#########################################
addi $t1,$t1,1
j jLoop
continue:
#####################################
# increment and Jump back
#####################################
addi $t0,$t0,1
j loop
################################################################################################################
############################################# sort END #######################################################
################################################################################################################
################################################################################################################
##### Procedure: Print
##### Info: Prints whatever is stored inside theString
#####
################################################################################################################
print:
####################################
# Print a new line
####################################
la $a0,newLine
li $v0,4
syscall
####################################
# Initialize incrementer for loop
####################################
add $t6,$zero,$zero # Set index i = 0 $t6
lprint:
#####################################
# Check for sentinal val and if true
# branch to done
#####################################
beq $t6,$s7,done
####################################
# Load Array[i] into t1 and print
####################################
add $t1,$s0,$t6
lb $a0, 0($t1) # Load argument
li $v0, 11 # Load opcode
syscall # Call syscall
#########################################
# increment and Jump back
#########################################
addi $t6,$t6,1
j lprint
################################################################################################################
############################################# print END ######################################################
################################################################################################################
################################################################################################################
##### Procedure: done
##### Info: Jumps to $ra. Only one procedure is needed to jump back to ra
################################################################################################################
done:
jr $ra
exit:
Antwoord 2, autoriteit 67%
regel 30: U gaat stap voor stap in uw array en wijzigt uw array-pointer.
Na de eerste en alle volgende forloops moet je het adres van je array opnieuw laden voordat je forloop opnieuw uitvoert, anders wijst het naar de verkeerde plaats.
Antwoord 3, autoriteit 67%
Hier is een stukje code voor Bubble sort in MIPS. Voer 10 ongesorteerd nummer in en dit zal de gesorteerde array terug afdrukken. Ik hoop dat dit helpt 🙂
.text
.globl main
main:
la $t1,array
li $s1,10
L1: beq $s1,$s2,L2
li $v0,5
syscall
sw $v0,0($t1)
addi $t1,$t1,4
addi $s2,$s2,1
j L1
li $s1,40
li $s2,0
li $s3,4
L2: beq $s1,$s2,printf
add $t1,$t1,$s2
lw $t0,0($t1) #a[i]
L3: beq $s3,$s1,incc
add $t1,$t1,$s3
lw $t2,0($t1) #a[j]
slt $t3,$t0,$t2
beq $t3,$0,swap
L4: addi $s3,$s3,4
j L3
swap:
sw $t0,0($t1)
sub $t1,$t1,$s2
sw $t2,0($t1)
j L4
incc:
addi $s2,$s2,4
j L2
printf:
la $t1,array
li $t0,0
li $v0,4
la $a0,print
syscall
li $s2,0
li $s1,10
L5: beq $s1,$s2,out
li $v0,1
lw $t0,0($t1)
move $a0,$t0
syscall
li $v0,4
la $a0,space
syscall
addi $s2,$s2,1
addi $t1,$t1,4
j L5
out:
li $v0,10
syscall
.end
.data
array: .word 0,0,0,0,0,0,0,0,0,0
print: .asciiz "\nthe sorted array : "
space: .asciiz " "
Antwoord 4
Probeer deze bellensoort eens. Alle regels hebben samengevat commentaar. Werkt prima op qtspim.
.data
arr: .word 10, 60, 40, 70, 20, 30, 90, 100, 0, 80, 50
space: .asciiz " "
.text
.globl main
main:
lui $s0, 0x1001 #arr[0]
li $t0, 0 #i = 0
li $t1, 0 #j = 0
li $s1, 11 #n = 11
li $s2, 11 #n-i for inner loop
add $t2, $zero, $s0 #for iterating addr by i
add $t3, $zero, $s0 #for iterating addr by j
addi $s1, $s1, -1
outer_loop:
li $t1, 0 #j = 0
addi $s2, $s2, -1 #decreasing size for inner_loop
add $t3, $zero, $s0 #resetting addr itr j
inner_loop:
lw $s3, 0($t3) #arr[j]
addi $t3, $t3, 4 #addr itr j += 4
lw $s4, 0($t3) #arr[j+1]
addi $t1, $t1, 1 #j++
slt $t4, $s3, $s4 #set $t4 = 1 if $s3 < $s4
bne $t4, $zero, cond
swap:
sw $s3, 0($t3)
sw $s4, -4($t3)
lw $s4, 0($t3)
cond:
bne $t1, $s2, inner_loop #j != n-i
addi $t0, $t0, 1 #i++
bne $t0, $s1, outer_loop #i != n
li $t0, 0
addi $s1, $s1, 1
print_loop:
li $v0, 1
lw $a0, 0($t2)
syscall
li $v0, 4
la $a0, space
syscall
addi $t2, $t2, 4 #addr itr i += 4
addi $t0, $t0, 1 #i++
bne $t0, $s1, print_loop #i != n
exit:
li $v0, 10
syscall