0
MIPS에서 선택 정렬을 구현하려고합니다. 때로는 제 출력물이 정확하지만 몇 가지 경우가 있습니다. 일반적으로 어떤 지점까지 그리고 그 지점 이후에 숫자들은 정렬되지 않은 상태로 출력됩니다. 또한 여러 음수로 어려움이있는 것으로 보입니다.선택 정렬의 MIPS 구현 올바른 값을 출력
이 문제는 스왑 기능과 관련이 있다고 생각하지만 확실하지 않습니다. 도움을 주시면 대단히 감사하겠습니다.
참고 : bge 또는 이동과 같은 의사 명령어는 사용할 수 없습니다.
여기 에뮬레이트하는 C 구현의 코드가 있습니다.
.data
msg1: .asciiz "The elements sorted in ascending order are:"
.align 2
space: .asciiz " "
.align 2
comma: .asciiz ","
.align 2
arr: .space 80
.text
MAIN:
# Ask for user input and put value in $s1
addi $v0, $zero, 5 # call service 5 for integer input
syscall # read integer
add $s1, $zero, $v0 # Save $t0 = len
# Load address for arr
la $s0, arr # Pointer to arr goes in $t1
add $a0, $zero, $s0 # Save arr pointer to $a0
add $a1, $zero, $s1 # Save len to $a1
# Ask for user input to fill arr
jal FILL
# Sort the list using selection sort
jal SORT
# Print list
jal PRINT
# Call to end program
addi $v0, $zero, 10 # system call for exit
syscall
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
FILL: # deal with stack and save
addi $t0, $zero, 0 # $t0 = counter = 0
FILL_LOOP:
slt $t1, $t0, $a1 # if(counter < len) continue
beq $t1, $zero, FILL_RETURN # if(counter >= len) branch out of loop
addi $v0, $zero 5 # call service 5 for integer input
syscall # read integer
addi $t2, $zero, 0 # clear $t2 and set to 0
add $t2, $zero, $v0 # $t2 holds input integer
add $t3, $zero, $t0 # $t3 = i
sll $t3, $t3, 2 # $t3 = counter * 4
add $t3, $t3, $a0 # addr of arr[counter]
sw $t2, 0($t3) # store values in arr
addi $t0, $t0, 1 # counter = counter + 1
j FILL_LOOP
FILL_RETURN:
jr $ra # Return
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
SORT:
addi $sp, $sp, -28 # make space for variables
sw $a0, 0($sp) # store $a0 (arr)
sw $a1, 4($sp) # store $a1 (len)
sw $ra, 8($sp) # store return address
sw $s0, 12($sp) # store $s0 (i)
sw $s1, 16($sp) # store $s1 (j)
sw $s2, 20($sp) # store $s2 (tmp)
sw $s3, 24($sp) # store $s3 (minIndex)
addi $s0, $zero, 0 # i = 0
add $t0, $zero, $a1 # $t0 = len
addi $t0, $t0, -1 # $t0 = len - 1
FOR_1:
slt $t1, $s0, $t0 # i < $t0 = len - 1 continue
beq $t1, $zero, SORT_RETURN # if !(i < len - 1) branch out of loop
add $s3, $zero, $s0 # minIndex = i
addi $t1, $s0, 1 # $t1 = i + 1
add $s1, $zero, $t1 # j = $t1 = i + 1
FOR_2:
slt $t1, $s1, $a1 # j < len continue
beq $t1, $zero, IF_1 # if !(j < len) branch out of loop
IF_2: # "FIND MIN"
# get value at arr[ j ] store in $t3
add $t2, $zero, $s1 # calculate index $t2 = j
sll $t2, $t2, 2 # offset = $t2 * 4
add $t2, $t2, $a0 # add offset to base address
lw $t3, 0($t2) # load value at arr[ j ] into $t3
# get value at arr[minIndex] store in$t5
add $t4, $zero, $s3 # calculate index $t4 = minIndex
sll $t4, $t4, 2 # offset = $t4 * 4
add $t4, $t4, $a0 # add offset to base address
lw $t5, 0($t4) # load value at arr[minIndex] into $t5
slt $t1, $t3, $t5 # if(arr[ j ] < arr[minIndex]) continue
beq $t1, $zero, LOOP_2 # if !(arr[ j ] < arr[minIndex]) branch out of if stmt
add $s3, $zero, $s1 # minIndex = j
LOOP_2:
addi $s1, $s1, 1 # j++
j FOR_2
IF_1: # "SWAP"
beq $s3, $s0, LOOP_1 # if(minIndex == i) branch out of if stmt (jump to LOOP_1)
# tmp = arr[minIndex]
add $t2, $zero, $s3 # calculate index $t2 = minIndex
sll $t2, $t2, 2 # offset = $t2 * 4
add $t2, $t2, $a0 # add offset to base address
lw $s2, 0($t2) # $s2 = tmp = arr[minIndex]
# arr[minIndex] = arr[ i ]
add $t3, $zero, $s0 # calculate index $t3 = i
sll $t3, $t3, 2 # offset = $t2 * 4
add $t3, $t3, $a0 # add offset to base address
lw $t0, 0($t3) # $t0 = arr [ i ]
sw $t0, 0($t2) # store value at arr[ i ] in arr[minIndex]
# arr[ i ] = tmp
sw $s2, 0($t3) # store tmp value in arr[ i ]
LOOP_1:
addi $s0, $s0, 1 # i++
j FOR_1
SORT_RETURN:
lw $a0, 0($sp) # Get $a0
lw $a1, 4($sp) # Get $a1
lw $ra, 8($sp) # Get return address
lw $s0, 12($sp) # Get $s0
lw $s1, 16($sp) # Get $s1
lw $s2, 20($sp) # Get $s2
lw $s3, 24($sp) # Get $s3
addi $sp, $sp 28 # Adjust stack pointer
jr $ra # Return
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
PRINT:
addi $t0, $zero, 0 # $t0 = counter = 0
add $t1, $zero, $a0 # $t1 = arr address pointer
# Print msg1
la $s3, msg1
add $a0, $zero, $s3 # put address of space in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string
# Print a space
la $s3, space
add $a0, $zero, $s3 # put address of space in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string
PRINT_LOOP:
slt $t2, $t0, $a1 # if(counter < len) continue
beq $t2, $zero, PRINT_RETURN # if(counter >= len) branch out of loop
add $t3, $zero, $t0 # $t3 = counter
sll $t3, $t3, 2 # $t3 = counter * 4
add $t3, $t3, $t1 # $t3 = addr of arr[counter]
lw $t4, 0($t3) # Load value to print
add $a0, $zero, $t4 # put address of $t4 in $a0 to print
addi $v0, $zero, 1 # call service 1 to print integer
syscall # print integer
# Check if last array element
# Skip printing comma and space
addi $t3, $a1, -1 # $t3 = len - 1
beq $t3, $t0, PRINT_RETURN # if(at least element)
# Print a comma
la $s3, comma
add $a0, $zero, $s3 # put address of space in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string
# Print a space
la $s3, space
add $a0, $zero, $s3 # put address of space in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string
addi $t0, $t0, 1 # counter - counter + 1
j PRINT_LOOP
PRINT_RETURN:
jr $ra # Return
C 꼬마 도깨비
for (c = 0 ; c < (n - 1) ; c++)
{
position = c;
for (d = c + 1 ; d < n ; d++)
{
if (array[position] > array[d])
position = d;
}
if (position != c)
{
swap = array[c];
array[c] = array[position];
array[position] = swap;
}
}