Рекурсивная быстрая сортировка в mips

надеюсь, у вас всех хорошего дня

Итак, я прохожу курс по MIPS и получил домашнее задание которую я решил, но обнаружил проблему, которую не мог решить уже 2 дня .... Итак, вопрос заключается в переводе этого кода Быстрая сортировка в MIPS и создании некоторых функций для печати и чтения элементов, введенных пользователем. моя проблема в быстрой сортировке.

void quick_sort(int array[], int n) {
 int i = 0; // i = low index
 int j = n-1; // j = high index
 int pivot = array[(i+j)/2]; // pivot = middle value
 while (i <= j) {
 while (array[i] < pivot) i++;
 while (array[j] > pivot) j--;
 if (i <= j) {
 int temp = array[i];
 array[i] = array[j]; // swap array[i]
 array[j] = temp; // with array[j]
 i++;
 j--;
 }
 }
 if (j > 0) quick_sort(&array[0], j+1); // Recursive call 1
 if (i < n-1) quick_sort(&array[i], n-i); // Recursive call 2
} 

вот мой главный

.data
 hi: .asciiz"Please Enter the number of elements greater than 1\n"
 elements : .asciiz " Please enter the elements \n"
print1:.asciiz"Array before sorting\n"
print2:.asciiz"Array after sorting\n "
comma : .asciiz","
space : .asciiz"\n"
array: .space 32
.text
start:
la $a0 , hi   # enter elements
li $v0 , 4
syscall

li $v0 , 5    # number of elements greater than 1
syscall
ble $v0 , 1 , start
move $s0, $v0  # save number of elements  n = $s0

la $a0 , elements  #enter elements string
li $v0 , 4
syscall

sll $a0 , $s0 , 2   # number of bytes to allocate ( 4 bytes for each integer)
li $v0 , 9
syscall
move $s1 , $v0 # address of the array = $s1


move $a0 , $s0  #number of elements
move $a1 , $v0  #array address
jal read_array

la $a0 , print1   # befor sorting text
li $v0 , 4
syscall

move $a0 , $s0 #number of elements
move $a1 , $s1      # array address 
jal print_array  #printing array before sorting

#sorting
move $a0 , $s0  #number of elements
move $a1 , $s1       # array address 
jal quick_sort

la $a0 , print2   # After sorting text
li $v0 , 4
syscall

# after sorting 
move $a0 , $s0 #number of elements
move $a1 , $s1      # array address 
jal print_array  #printing array before sorting


li $v0 , 10
syscall

поэтому я вызываю функцию быстрой сортировки в "сортировочный" комментарий.

и это функция сама по себе

quick_sort:
add $s3 , $0 , $a1 # saving array address
sort_loop:


add $sp , $sp , -16 # storing the address
sw $ra , 0($sp) # return address
sw $a0 , 4($sp) # n
sw $a1 , 8($sp) # array address
sw $t0 , 12($sp) # i


li $t0 , 0    #i
add $t1 , $a0 ,-1  # j=n-1

#pivot 
add $t2 , $t0 , $t1 # i + j
srl $t2 , $t2 , 1 # (i+j)/2
#calculate the address for the pivot 
sll $t2 , $t2 ,2  # ((i+j)/2) * 4
add $t3 , $a1 , $t2   # &array + ((i+j)/2) * 4 ( address of the pivot)
lw $t4 , 0($t3) # Pivot value
#============
#while loop
while_main:
bgt $t0 , $t1 , after_if # while i <= j
while_i:
sll $t5 , $t0 , 2  # i * 4
add $t8 , $t5 , $a1 # &array + (i*4) (address of the ith value)
lw $t5 , 0($t8)  # value of ith
bge $t5 , $t4 , while_j # if (array[i] >= pivot ) skip
add $t0 , $t0 , 1 #i++
j while_i
while_j:
sll $t6 , $t1 , 2 # j*4
add $t9 , $t6 , $a1 #  &array + (j*4) (address of the jth value)
lw $t6 , 0($t9)  # value of jth
ble $t6 , $t4 , if # if (array[j] <= pivot ) skip
add $t1 , $t1 , -1 #j--
j while_j
if:
bgt $t0 , $t1 , after_if  # if (i>=j) skip
sw $t6 , 0($t8) # array[i] = array[j]
sw $t5 , 0($t9) # array[j] = old array[i]
add $t0 , $t0 , 1 #i++
add $t1 , $t1 , -1 #j--
j while_main
after_if:
#end of while_main loop
#recursive #1
r1:
blez $t1 , r2  # if (j <=0) skip
add $a0 , $t1, 1   # n = j+1
add $a1 , $0 , $s3 # address of the array a1  
jal sort_loop




#recursive #2
r2:
add $t7 , $a0 , -1 # n-1
bge $t0 , $t7 , done # if (i>= n-1) skip

sll $s2 , $t0 , 2  # i * 4
add $a1 , $s3 , $s2 # &array + (i*4) (address of the ith value)
#add $a1 , $t8 , $0  # address of the ith element
add $a0 , $t7 , $0  # n = n-1
jal sort_loop


done :
lw $ra , 0($sp) # return address
lw $a0 , 4($sp) # n
lw $a1 , 8($sp) # array address
lw $t0 , 12($sp) # i
add $sp , $sp , 16 # unallocationg
jr $ra

поэтому он работает и сортирует, но с некоторыми элементами он не работает например, если я ввожу 10 9 8 7 6 5 4 3 21 он будет сортировать, но если 10 9 6 4 5 3 2 1 8 7 это покажет выход

что я не мог понять, почему, если исходный код неверен. надеюсь, что я могу получить помощь :) (мой срок - через 30 ч.>.>)

Спасибо ^ _ ^

я могу дать вам весь код, если нужно

GuestA 26.10.2018 06:51

Используйте функции отладки симулятора для пошагового выполнения кода, чтобы вы могли анализировать поведение во время выполнения.

Michael 26.10.2018 08:25

У меня закружилась голова, и я не смог этого сделать. Я только что понял, что делаю n-1 на 2-м рекурсивном, а не n-i X, x, и я должен загрузить n перед этим тоже, так что это лучше, но ... это еще не решено

GuestA 26.10.2018 12:11
0
3
1 424
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

так что решение такое

//////
after_if:

sw $t0 , 12($sp) # i ( stored after modification)
#end of while_main loop
#recursive #1
r1:
blez $t1 , r2
add $a0 , $t1, 1   # n = j+1
jal quick_sort




#recursive #2
r2:
lw $a0 , 4($sp) # n (restored)
lw $t0 , 12($sp) # i (restored)

add $t7 , $a0 , -1 # n-1
bge $t0 , $t7 , done
sll $s2 , $t0 , 2  # i * 4
add $a1 , $a1 , $s2 # &array + (i*4) (address of the ith value)
sub $a0 ,$a0  , $t0  # n = n-i
jal quick_sort
//////

я должен был сохранить (я) после того, как он был изменен

и мне вообще не нужно было перезагружать адрес, что было моей самой большой ошибкой

и мне нужно перезагрузить значения n и i для второй рекурсии

Тай для тех, кто это читал и пытался помочь

Другие вопросы по теме