• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Migueeeeeel

Quicksort Mips

4 mensagens neste tópico

Boas, eu tenho andado a tentar aprender MIPS, e para começar fiz um quicksort simples em C e estou a tentar converter-lo para MIPS. Mas estou a ter problemas, possivelmente variaveis trocadas no ciclo while do codigo em MIPS. Se alguém me poder ajudar a descobrir onde o programa (e eu  :)) está a falhar fico agradecido.

em C

#include<stdio.h>

void qsort(int[], int, int);
int partition(int[], int, int);
void swap(int[], int, int);

main() {
  int a[] = {7,12,1,2,0,15,4,11,9};
  int size = 8;
  
  printf("Array por Ordenar: ");
  int i;
  for(i=0;i<size+1;i++)
    printf("%d ",a[i]);

  qsort(a,0,size);

  printf("\n\nArray Ordenada: ");
  for(i=0;i<size+1;i++)
    printf("%d ",a[i]);
  printf("\n");
}


void qsort(int a[], int z, int l){
  if(z >= l) return;
  int index = partition(a,z,l);
  qsort(a,z,index-1);
  qsort(a,index+1,l);
}

int partition(int a[], int z, int l){
  int pivot = a[z], i=z, index=z;
  
  swap(a, z, l);
  for(i = z; i < l; i++){
    if(a[i] < pivot){
      swap(a,i,index);
      index += 1;
    }
  }
  swap(a,l,index);
  
  return index;
}

void swap(int a[], int i, int j)
{
    int t  = a[i];
    a[i] = a[j];
    a[j] = t;
}

e em MIPS

.data

numbers: .word 3,5,7,8,9,0,11,2,5,7,8
size:  .word 11
str:	   .asciiz " "
str1:    .asciiz "3 5 7 8 9 0 11 2 5 7 8\n"
str2:	   .asciiz "\n"

.text
.globl main

main:
    la $a0, numbers   # $a0 = array
    move $a1, $zero   # $a1 = 0
    lw $a2, size      # $a2 = size
    sub $a2,$a2,1     # size - 1
    
    jal qsort         # (array,0,n-1)
    
    # print the array
    la $a0,str1       # Print of str1, starting array, for comparison
    li $v0,4                 
    syscall
    

 # print new sorted array
 la $t2,numbers
  	 lw $t4,size
 li $t3,0

for_print:
  bge  $t3, $t4, exit_print	 # if test >= size go to exit_print

        sll $t1, $t3, 2      	   	 # $t1 = test*4
  add $t1, $t1, $t2    	  	 # $t2 = numbers + test*4

        lw   $a0,0($t1)
        li   $v0,1              	 # print of the element numbers[test]
        syscall                  

  la   $a0,str    	  	 # print newline
  li   $v0,4                
    	  syscall

        addi $t3,$t3,1            	 # test = test + 1
        j    for_print

exit_print:

  li $v0,10				 # syscall to exit
  syscall

qsort:
# create stack frame and save vals
addi $sp, $sp, -16

sw   $ra, 0($sp)
sw   $s0, 12($sp)
sw   $s1, 8($sp)
sw   $s2, 4($sp)
      ###

bge $a1,$a2,end_qsort_if	# if(z >= l) return;
    
#save contents in s registers
#s0 = array, s1 = z, s2 = l

# int index = partition(a,z,l);
move $s0,$a0
move $s1,$a1
move $s2,$a2

jal partition

move $s3,$v0			# store pivotPosition in $s3
sub  $t0,$s3,1			# pivotPosition-1 = $t0
# qsort(a,z,index-1);
move $a0,$s0
move $a1,$s1
move $a2,$t0

jal qsort
    # qsort(a,index+1,l);
move $a0,$s0
addi $a1,$s3,1
move $a2,$s2

jal qsort

end_qsort_if:
      # restore values
lw   $ra, 0($sp)
lw   $s0, 12($sp)
lw   $s1, 8($sp)
lw   $s2, 4($sp)

addi $sp, $sp, 16
      ###

jr $ra				#return


# do some swapping, return "right" in $v0
# a0 = array, a1 = z, a2 = l
partition:

    # create stack frame and save vals
addi $sp, $sp, -24

sw   $ra, 4($sp)
sw   $s0, 8($sp)
sw   $s1, 12($sp)
sw   $s2, 16($sp)
sw   $s3, 20($sp)
sw   $s4, 0($sp)

      ###
    move $s1, $a1	#s1 = z
    # pivot = a[z] 
    move $s3,$s1	#s3 = pivot = a[z]
    sll  $s3,$s1,2
add  $s3,$s0,$s3
lw   $s3, 0($s3)
    # i = z
    move $s4, $s1
    # index = z
    move $s2,$s1
    jal swap

while:
    bge  $t1,$a2,end_while		# if i >= l, end while
    sll $t1, $a1, 2      # $t1 = i
    add $t1, $t1, $a0    # $t1=a+i*4
    lw  $t3, 0($t1)      # $t0=a[i] 
    #bge  $t3, $t2,end_if		# if i[i]] >= pivot
    slt  $t0,$t3,$t2    # if a[i] < pivot
    beq  $t0,$0,$end_if
    #move $a0,$s0
move $a1,$s1
move $a3,$a2
move $a2,$s2 
    jal swap
    add  $s2, $s2, 1        # index ++
    add  $s4, $s4,1
    j while
end_if:
    add  $s4, $s4,1
    j while
end_while:
    move $a0,$s0
    move $a1,$a3
    move $a2,$s2
    jal swap
    move $v0,$s2	# return index

      # restore values
lw   $ra, 4($sp)
lw   $s0, 8($sp)
lw   $s1, 12($sp)
lw   $s2, 16($sp)
lw   $s3, 20($sp)
lw   $s4, 0($sp)

addi $sp, $sp, 24
      ###

jr   $ra  
swap:
    sll $t1, $a1, 2      # $t1 = i
    add $t1, $t1, $a0    # $t1=a+i*4
    lw  $t0, 0($t1)      # $t0=a[i] 

    sll $t2, $a2, 2      # $t2=j
    add $t2, $t2, $a0    # $t2=a+j*4
    lw  $t3, 0($t2)      # $t3=a[j]

    sw  $t3, 0($t1)      # a[i]=$t3  
    sw  $t0, 0($t2)      # a[j]=$t0

    jr  $ra

Obrigado desde já a quem poder ajudar.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É muito código para estar a entender isso tudo...

Uma sugestão: uma um debugger/simulador para ir seguindo o código e assim vês mais facilmente onde está o problema.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Antes de mais, obrigado pela resposta. Eu tenho andado a utilizar o SPIM, mas o programa não é muito intuitivo. Mas vou continuar a tentar, e se conseguir descobrir o problema posto aqui.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

.data
array:	.word 6,5,-2,3,2,1
.text

main:
li	$a0, 0			# carrega begin em $a0 para passar como parametro
li	$a1, 20			# carrega end em $a1 para passar como parametro
li	$a2, -1
li	$a3, -1
jal quickSort		# chama quickSort

li 	$v0, 10			# system call for exit
syscall				# Exit!


quickSort:
.data
	end:	.word 0
	begin:	.word 0 
	pivot:	.word 0
	left:	.word 0 
	right:	.word 0
.text


#salva na pilha de execucao
addiu	$sp,$sp,-20		# Aloca espaço na pilha para 1 palavra (8 bytes)
sw	$a0, 0($sp)			# salva begin
sw	$a1, 4($sp)			# salva left
sw	$a2, 8($sp)			# salva right
sw	$a3, 12($sp)		# salva end	
sw	$ra, 16($sp)		# salva endereco da chamada
#fim salvamento na pilha


sw	$a0, begin			# guarda begin na memoria
sw	$a1, end			# guarda end na memoria

lw	$s0, begin			# $s0 = begin
lw	$s1, end			# $s1 = end

sub	 $t9, $s1, $s0		# $s9 = end - begin
bgtz $t9, e				# if(end - begin > 0) e
j fim					# else -> fim


e:	lw	$s2, array($s0)		# $s2 = array[begin]
sw	$s2, pivot			# pivot = array[begin]

addi $s3, $s0, 4		# left = begin + 1
sw	$s3, left

lw	$s4, end			# right = end
sw	$s4, right



while:
bge $s3, $s4, a			# if(left >= right) a
lw	$s5, array($s3)		# $s5 = array[left]
ble	$s5, $s2, incLeft	# if(array[left] <= pivot) incLeft
						# else

lw	$s6, array($s4)		# $s6 = array[right]
lw	$s5, array($s3)		# $s5 = array[left]

sw	$s5, array($s4)		# array[right] = array[left]
sw	$s6, array($s3)		# array[left] = array[right]

addi $s4, $s4, -4		# right--
sw	$s4, right

lw	$s5, array($s3)		# $s5 = array[left]
lw	$s6, array($s4)		# $s6 = array[right]
j while

a:	lw	$s5, array($s3)		# $s5 = array[left]
lw	$s6, array($s4)		# $s6 = array[right]
bgt	$s5, $s2, decLeft	# if(array[left] > pivot) decLeft

c:	lw	$s7, array($s0)		# $s7 = array[begin]
lw	$s5, array($s3)		# $s5 = array[left]

sw	$s7, array($s3)		# array[left] = array[begin]
sw	$s5, array($s0)		# array[begin] = array[left]

lw	$s7, array($s0)		# $s7 = array[begin]
lw	$s5, array($s3)		# $s5 = array[left]


#chama quickSort primeira parte
lw	$a0, begin		# $a0 = begin primeira
lw	$a1, left		# $a1 = left
lw	$a2, right		# $a2 = right
lw	$a3, end		# $a3 = end

addi $a1, $a1, -4	# $a1 = left-1
addi $t0, $a1, 4	# $t0 = left

jal quickSort		# chama quickSort
#fim recursao primeira parte


sw	$a0, begin			# guarda begin na memoria
sw	$a1, left			# guarda left na memoria
sw	$a2, right			# guarda right na memoria
sw	$a3, end			# guarda end na memoria


#chama quickSort segunda parte
lw	$a0, right		# $a0 = right segunda
lw	$a1, end		# $a1 = end
lw	$a2, begin		# $a2 = begin
lw	$a3, left		# $a3 = left

jal quickSort		# chama quickSort
#fim recursao segunda parte



fim:
lw	$ra, 16($sp)	# endereco
lw	$a3, 12($sp)	# end
lw	$a2, 8($sp)		# right
lw	$a1, 4($sp)		# left
lw	$a0, 0($sp)		# begin

sw	$zero, 16($sp)	# endereco
sw	$zero, 12($sp)	# end
sw	$zero, 8($sp)	# right
sw	$zero, 4($sp)	# left
sw	$zero, 0($sp)	# begin

addiu $sp, $sp, 20 	# desaloca espaço na pilha para (20 bytes)

jr $ra


incLeft:
addi $s3, $s3, 4
sw	$s3, left
j while

decLeft:
addi $s3, $s3, -4
sw	$s3, left
j c

esse quicksort funciona

fiz no Mars

não se se vai adiantar pq já faz muito tempo

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora