-
Notifications
You must be signed in to change notification settings - Fork 0
/
bubble_sort.asm
182 lines (154 loc) · 3.36 KB
/
bubble_sort.asm
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
.data
array_size_prompt: .asciiz "Enter the size of the array: "
array_element_prompt: .asciiz "Enter the array element element: "
array_print_message: .asciiz "The array elements are: "
illegal_array_size_message: .asciiz "The array size should be positive."
unsorted_array_message: .asciiz "The unsorted array is:\n"
sorted_array_message: .asciiz "The sorted array is:\n"
.text
main:
# reading array size
# and storing it in $s0
li $v0, 4
la $a0, array_size_prompt
syscall
li $v0, 5
syscall
move $s0, $v0
# if array size <= 0, exit
blez $s0, illegal_array_size
# allocating memory for array
# and storing the address in $s1
li $v0, 9
move $a0, $s0
sll $a0, $a0, 2
syscall
move $s1, $v0
# reading array elements
# and storing them in the array
li $t0, 0
move $t1, $s1
read_array_loop:
bge $t0, $s0, read_array_loop_end
li $v0, 4
la $a0, array_element_prompt
syscall
li $v0, 5
syscall
sw $v0, ($t1)
addi $t0, $t0, 1
addi $t1, $t1, 4
j read_array_loop
read_array_loop_end:
# printing the array
li $v0, 4
la $a0, unsorted_array_message
syscall
move $a0, $s1
move $a1, $s0
jal print_array
# sorting the array
move $a0, $s1
move $a1, $s0
jal bubble_sort
# printing a sorted array
li $v0, 4
la $a0, sorted_array_message
syscall
move $a0, $s1
move $a1, $s0
jal print_array
# jumping to exit
j exit
# bubble sort procedure
# accepts array address in $a0
# and array size in $a1
bubble_sort:
# popping out values on a stack
addi $sp, $sp, -12
sw $ra, 8($sp)
sw $a0, 4($sp)
sw $a1, 0($sp)
# outer loop
# $t0 -- counter, $t1 -- outer loop limit
li $t0, 0
lw $t1, 0($sp)
sub $t1, $t1, 1
outer_loop:
bge $t0, $t1, outer_loop_end
# inner loop
li $t2, 0
sub $t3, $t1, $t0
inner_loop:
bge $t2, $t3, inner_loop_end
# loading array elements
# $t4 -- array + i, $t5 -- array + i + 1
# $t6 -- array[i], $t7 -- array[i + 1]
lw $t4, 4($sp)
sll $t6, $t2, 2
add $t4, $t4, $t6
lw $t6, ($t4)
lw $t5, 4($sp)
sll $t7, $t2, 2
add $t5, $t5, $t7
addi $t5, $t5, 4
lw $t7, ($t5)
ble $t6, $t7, else_branch
# swapping array elements
sw $t7, ($t4)
sw $t6, ($t5)
else_branch:
addi $t2, $t2, 1
j inner_loop
inner_loop_end:
addi $t0, $t0, 1
j outer_loop
outer_loop_end:
# restoring values from stack and returning
lw $ra, 8($sp)
addi $sp, $sp, 12
jr $ra
# procedure for printing an array
# accepts array address in $a0
# and array size in $a1
print_array:
# popping out values on a stack
addi $sp, $sp, -12
sw $ra, 8($sp)
sw $a0, 4($sp)
sw $a1, 0($sp)
# printing array elements
li $t0, 0
lw $t1, 0($sp)
print_array_loop:
bge $t0, $t1, print_array_loop_end
lw $a0, 4($sp)
sll $t2, $t0, 2
add $a0, $a0, $t2
lw $a0, ($a0)
li $v0, 1
syscall
li $v0, 11
li $a0, ' '
syscall
addi $t0, $t0, 1
j print_array_loop
print_array_loop_end:
# printing a new line
li $v0, 11
li $a0, '\n'
syscall
# restoring values from stack and returning
lw $ra, 8($sp)
addi $sp, $sp, 12
jr $ra
# if the size is <= 0, break
illegal_array_size:
li $v0, 4
la $a0, illegal_array_size_message
syscall
j exit
# program endpoint
exit:
li $v0, 10
syscall