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
| QuickSort.s
.data # Data declaration section
array: .word 2,4,15,10,8,8,7,3
title: .asciiz "Demonstration of QuickSort"
before: .asciiz "\nString before: "
after: .asciiz "\nString after: "
.text
main: # Start of code section
li $v0, 4
la $a0, title
syscall
la $a0, before
syscall
lw $a0, array
syscall
# Call on QuickSort
lw $a0, array # Constant pointer to string
add $a1, $a0, 0 # Pointer to left end
add $a2, $a0, 25 # Pointer to right end
jal QS # The one call from main
# Print out results
lw $a0, after
li $v0, 4
syscall
lw $a0, array
syscall
# End main
li $v0, 10
syscall
##
# Recursive QuickSort
# $a0 -> array (constant) - Global
# $a1 -> left end, $a2 -> right end
##
QS: sub $sp, $sp, 16 # \
sw $a1, 0($sp) # \
sw $a2, 4($sp) # > Save registers
sw $t2, 8($sp) # /
sw $ra, 12($sp) # / and return address
# Basecase
bge $a1, $a2, QSret # Nothing to sort
# Partition using middle element as pivot
# A[a1..a2] -> A[a1..j-1] | A[j] | A[j+1..a2]
sub $t3, $a1, $a0 # index i
sub $t4, $a2, $a0 # index j
add $t0, $t3, $t4 # t0 = i+j choose middle
sra $t0, $t0, 1 # t0 = (i+j) div 2
add $t0, $t0, $a0 # t0 -> A[(i+j) div 2]
lb $t5, 0($t0) # t5 = pivot value
lb $t6, 0($a1) # t6 = A[i] = left element
sb $t5, 0($a1) # Swap them so pivot
sb $t6, 0($t0) # is first element
#
move $t1, $a1 # Initially i -> first (pivot) item a1
add $t2, $a2, 1 # Initially j -> just past last item a2
lb $t0, 0($a1) # Pivot value in t0 (in $t5)
#
loop:
#
i_loop: add $t1, $t1, 1 # i=i+1;
lb $t5, 0($t1) # t5 = A[i]
bgt $t0, $t5, i_loop # until pivot <= A[i]
j_loop: sub $t2, $t2, 1 # j=j-1;
lb $t6, 0($t2) # t6 = A[j]
blt $t0, $t6, j_loop # until pivot >= A[j]
#
bge $t1, $t2, test # if i<j swap
#
sb $t6, 0($t1) # A[i] and
sb $t5, 0($t2) # A[j]
#
test: blt $t1, $t2, loop # until i >= j
#
lb $t5, 0($a1) # swap a[a1] = pivot
lb $t6, 0($t2) # and a[j]
sb $t5, 0($t2) # now a[j] is
sb $t6, 0($a1) # in its final position
# Done with partition
lw $a1, 0($sp)
sub $a2, $t2, 1
jal QS # Recursive call on left
add $a1, $t2, 1
lw $a2, 4($sp)
jal QS # Recursive call on right
#
QSret: lw $ra, 12($sp) # \Replace return address
lw $t2, 8($sp) # \
lw $a2, 4($sp) # > and registers
lw $a1, 0($sp) # /
add $sp, $sp, 16 # /
jr $ra
## END OF QuickSort.s |
Tri rapide
(je debute en assembleur)
Répondre avec citation
Partager