Рекурсивная быстрая сортировка в 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
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
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 для второй рекурсии

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

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