quicksort-mips/quickSort at master · andercsilva/quicksort-mips · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
.data
	x: .word 8,5,9,0,2,6,7,1,3,4
	InitVet: .word 0
	FimVet: .word 10
.text
.globl main
# $s0 = X
# $s1 = InitVet
# $s2 = FimVet
# $s3 = Número de vetores
# $s4 = pivo
main:
	move $t5, $ra # salva o endereço de retorno
	la $s0, x
	lw $s1, InitVet
	lw $s2, FimVet
	addi $s3, $s2, -1
	jal inicio
	move $ra, $t5 #Salva o retorno
	j imprime
inicio:
# $t0 = i
# $t1 = j
	move $t6, $ra # salva o endereço de retorno
	move $t0, $s1 # i = InitVet
	move $t1, $s2 # j = FimVet
	jal pivo #Executa o pivo e espera o retorno
	move $ra, $t6 #Salva o retorno
	enquanto:
		blt $t0,$t1, executaEnquanto #enquanto (i < j) faça
			j fimEnquanto
		executaEnquanto:
		enquantoMenor: #enquanto (X[i] < pivo) faça
 			sll $a3, $t0, 2 # $a3 = i * 4
      			add $a3, $s0, $a3 # $a3 = &x[i]
			lw $t5, 0($a3) # $t5 = x[i]

			#imprime $t5
			#li $v0, 1 #define o serviço
			#move $a0, $t5 #define a posição do vetor a ser impresso
			#syscall #imprime o valor de i
			#imprime $s4
			#li $v0, 1 #define o serviço
			#move $a0, $s4 #define a posição do vetor a ser impresso
			#syscall #imprime o valor de i

			blt $t5,$s4, somaMenor #enquanto (X[i] < pivo) faça
				j fimEnquantoMenor
			somaMenor:
	      			addi $t0, $t0, 1      # i = i + 1
	      			j enquantoMenor
	      	fimEnquantoMenor:

      		enquantoMaior: # enquanto (X[j] > pivo) faça
      			sll $a3, $t1, 2       # $a3 = j * 4
			add $a3, $s0, $a3     # $a3 = &x[j]
      			lw $t7, 0($a3)        # $t7 = x[j]

			#imprime $t7
			#li $v0, 1 #define o serviço
			#move $a0, $t7 #define a posição do vetor a ser impresso
			#syscall #imprime o valor de i
			#imprime $s4
			#li $v0, 1 #define o serviço
			#move $a0, $s4 #define a posição do vetor a ser impresso
			#syscall #imprime o valor de i

      			bgt $t7, $s4, somaMaior
      				j fimEnquantoMaior
      			somaMaior:
      				addi $t1, $t1, -1
      				j enquantoMaior
      		fimEnquantoMaior:

		ble $t0,$t1,entao
			j fimSe
		entao:
			sll $a3, $t0, 2 # $a3 = i * 4
			add $a3, $s0, $a3 # $a3 = &x[i]
			lw $t5, 0($a3) # $t5 = x[i]
			sll $t2, $t1, 2 # $a3 = j * 4
			add $t2, $s0, $t2 # $a3 = $x[j]
			lw $t7, 0($t2) # $t7 = x[j]
			sw $t7, 0($a3)
			sw $t5, 0($t2)
			addi $t0, $t0, 1
			addi $t1, $t1, -1
		fimSe:


	fimEnquanto:


	bgt $t1, $s1, entao2
		j fimEntao2
	entao2:
		move $s2, $t1
		j inicio
	fimEntao2:
	bgt $t0, $s2, entao3
		j fimEntao3
	entao3:
		move $s1, $t0
		j inicio
	fimEntao3:
	jr $ra
pivo:
	add $a0, $s1, $s2 # InitVet + FimVet
	li $a1, 2
	div $a0, $a1 # (InitVet + FimVet) div 2
	mflo $a3
	sll $a3, $a3, 2 # $a3 = i * 4
	lw $s4, x($a3)
	jr $ra #retorna para inicio no ponto salvo
imprime:
	li $t8, 0
	li $t9, 40
	loop:
	li $v0, 1 #define o serviço
	lw $t2, x($t8)
	move $a0, $t2 #define a posição do vetor a ser impresso
	syscall #imprime o valor de i
	addi $t8, $t8, 4 #i++ alinhando com a memória 4 bytes por palavra
	bne $t8, $t9, loop #se não é o fim do laçõ, volta para loop