Problema Assembly MIPS - IDE MARS

felipe32444
(usa Ubuntu)

Enviado em 14/04/2024 - 00:38h

Estou tentando resolver um problema da faculdade com o objetivo de traduzir o seguinte código abaixo, é um quicksort com escolha de pivo sendo o valor do meio. Minha dúvida é saber se minha lógica está correta de seguir dessa forma ou se estou errando algo. Segue o quicksort em C e em seguida o meu código em assembly MIPS.:

QuickSort em C:

void quicksort(int* array, int low, int high)
{
int i = low, j = high; // low and high index
int pivot = array[(low+high)/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 (low < j) quick_sort(array, low, j); // Recursive call 1
if (i < high) quick_sort(array, i, high); // Recursive call 2
}

Meu código:

.data
array: .space 200 # Reserva espaço para 50 inteiros
msg_lenght_array: .asciiz "Digite o tamanho do array: "
msg_value_array: .asciiz "Digite o valor do array: "
.text
main:
move $t0, $zero # Inicialize o índice do array

# Imprime mensagem para pegar o tamanho do array
li $v0, 4
la $a0, msg_lenght_array
syscall

# Recebe quantas posições do array
li $v0, 5
syscall
move $t1, $v0 # Armazena o número de posições do array em $t1

# Define o tamanho do array
li $t3, 4
mul $t2, $t1, $t3 # Multiplica o número de posições pelo tamanho de cada elemento do array
move $s1, $t3 # salva o tamanho do array em número em $s1

input_loop:
# Verificação de saída
beq $t0, $t2, sai_do_input_loop

# Imprime mensagem para pegar o valor
li $v0, 4
la $a0, msg_value_array
syscall

# Pega o valor e armazena no array
li $v0, 5
syscall
sw $v0, array($t0) # Armazena o valor lido no array

# Incrementa o valor para a próxima posição
addi $t0, $t0, 4
j input_loop

sai_do_input_loop:

#Atribui os valores para i e j iniciais, respectivamente $t4 e $t5, low e high iniciais
move $t4, $zero #inicia como 0, int low inicial
move $t5, $s1 #inicia com o tamanho do array, int high inicial

quick_sort: #quicksort(int* array, int low, int high)

move $t6, $t4 # int i = low
move $t7, $t5 # int j = high

# Mensagem de depuração: Mostra o valor de low e high
li $v0, 4
la $a0, msg_low_high
syscall
li $v0, 1
move $a0, $t4
syscall
li $v0, 1
move $a0, $t5
syscall

# Calcula o índice médio
add $s2, $t4, $t5 # $s2 = low + high

# Mensagem de depuração: Mostra o valor de s2 antes do shift
li $v0, 4
la $a0, msg_s2
syscall
li $v0, 1
move $a0, $s2
syscall

srl $s2, $s2, 1 # $s2 = (low + high) / 2

# Mensagem de depuração: Mostra o valor de s2 após o shift
li $v0, 4
la $a0, msg_s2_shifted
syscall
li $v0, 1
move $a0, $s2
syscall

mul $s2, $s2, $t3 # Multiplica s2 por quatro para encontrar a posição
lw $s5, array($s2) # pivot = conteúdo da posição (low + high) / 2 do array

# Mensagem de depuração: Mostra o valor do pivô
li $v0, 4
la $a0, msg_pivot
syscall
li $v0, 1
move $a0, $s5
syscall

loop_i_menorigual_j: #while(i <= j)
bgt $t6, $t7, sai_do_loop_i_menorigual_j #condição de saída do loop inicial

loop_arrayi_menor_pivot:
mul $s3, $t6, $t3 # multiplica i por 4 para encontrar a posição do i
lw $s6, array($s3) # array[i]
bge $s6, $s5, sai_do_loop_arrayi_menor_pivot
addi $t6, $t6, 1 #i++
j loop_arrayi_menor_pivot

sai_do_loop_arrayi_menor_pivot:

loop_arrayj_maior_pivot:
mul $s3, $t7, $t3 # multiplica j por 4 para encontrar a posição do j
lw $s7, array($s3) # array[j]
ble $s7, $s5, sai_do_loop_arrayj_maior_pivot
subi $t7, $t7, 1 # j--
j loop_arrayj_maior_pivot

sai_do_loop_arrayj_maior_pivot:

ble $t6, $t7, swap # if (i <= j) executa o swap
bgt $t6, $t7, not_swap # else pula essa etapa

swap:
lw $s4, array($t6) # int temp=array[i]
sw $s7, array($t6) # array[i]=array[j]
sw $s4, array($t7) # array[j]=temp
addi $t6, $t6, 1 # i++
subi $t7, $t7, 1 # j--
not_swap:
j loop_i_menorigual_j

sai_do_loop_i_menorigual_j:

blt $t4, $t7, recursive_call_1 # if (low < j)
recursive_call_1: # Recursive call 1
move $t5, $t7 # high = j
j quick_sort # Chama recursivamente o quick sort com o novo valor de high

blt $t6, $t5, recursive_call_2 # if (i < high)
recursive_call_2: # Recursive call 2
move $t4, $t6 # low = i
j quick_sort # Chama recursivamente o quick sort com o novo valor de low

input_loop_out:
move $t0, $zero
imprime:
beq $t0, $t2, saiDoImprime
li $v0, 1
lw $a0, array($t0) # Carrega o valor atual do array
syscall

addi $t0, $t0, 4
j imprime
saiDoImprime:
li $v0, 10
syscall