-
Notifications
You must be signed in to change notification settings - Fork 1
/
ca-II-handout-2.s
188 lines (164 loc) · 5.57 KB
/
ca-II-handout-2.s
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
183
184
185
186
187
188
# Authors: Fotis Ioannis, Gianopoulou Aikaterini
# ===================================================================================
# Description:
# This program takes an input of 40K 1-byte positive integers in range [1,127]
# 1. Checks if all its elements are inside the desired range
# 2. Sorts the array using the Dutch-National-Flag Quicksort implementation
# More information here: https://en.wikipedia.org/wiki/Dutch_national_flag_problem
# 3. Searches for a specific number's index in the sorted array with Binary-Search
# ===================================================================================
#
# QuickSort pseudocode:
# algorithm qSort(&array, low, high)
# if (low < high) then
# left, right <= threeWayPartition(&array, low, high)
# quicksort(&array, low, left - 1)
# quicksort(&array, right, high)
# end qSort
#
# procedure threeWayPartition (&array, low, high)
# pivot <= array[high]
# left, right <= low
# bound <= high
#
# while (right <= bound)
# if (array[right] < array[pivot])
# swap (array[left], array[right])
# left++
# right++
# else if (array[right] > array[pivot])
# swap (array[right], array[bound])
# bound--
# else right++
# return left, right
# end threeWayPartition
#
# ===================================================================================
#
# Binary Search pseudocode:
# algorithm bSearch (&array, low, high, x)
# index = mid(low, high)
# if (array[index] == x) return index
# if (array[index] < x) bSearch (&array, low, index-1, x)
# if (array[index] > x) bSearch (&array, index+1, high, x)
# return 0
# end bSearch
.text
.globl main
.set noreorder
main:
############## Part A - Check input numbers ##############
la $t0, array # t0 => arrayPtr = *array
li $t1, 39999 # t1 => arraySize - 1
add $t1, $t0, $t1 # t1 = *array + arraySize - 1
scan:
lb $t2, 0($t0) # t2 = array[i]
addi $t0, $t0, 1 # i++
blez $t2, exit # if (array[i] <= 0) abort execution
beq $t0, $t1, sort # while (*array < array[arraySize])
j scan
sort:
################### Part B - QuickSort ###################
la $a0, array # a0 => arrayPtr = *array
addi $a1, $zero, 0 # a1 => low = 0
li $a2, 39999 # a2 => high = arraySize - 1
jal qSort # sort array
################# Part C - Binary Search #################
la $s7, POS # s7 = &POS
addi $t8, $zero, 2 # divisor to calculate middle of array
addi $a3, $zero, 92 # a3 = x
jal bSearch # call bSearch(&array, low, high, x)
exit:
break
################ QuickSort Implementation ################
qSort: # void (int *array, int low, int high)
addi $sp, $sp, -20 # push down the stack
sw $ra, 0($sp) # store return address
sw $a1, 4($sp) # store a1 = low
sw $a2, 8($sp) # store a2 = high
sw $s0, 12($sp) # store s0 = index of left partition
sw $s1, 16($sp) # store s1 = index of right partition
slt $t9, $a1, $a2 # check low < high
beq $t9, $zero, return # if (low >= high) return
jal partition
recursiveLeft:
lw $a1, 4($sp) # restore a1
addi $a2, $s0, -1 # new high = left - 1
jal qSort # call quicksort(&array, low, left - 1)
recursiveRight:
lw $a2, 8($sp) # restore a2
addi $a1, $s1, 0 # new low = right
jal qSort # call quicksort(&array, right, high)
return:
lw $ra, 0($sp) # restore return address
lw $a1, 4($sp) # restore a1
lw $a2, 8($sp) # restore a2
lw $s0, 12($sp) # restore s0
lw $s1, 16($sp) # restore s1
addi $sp, $sp, 20 # pull up the stack
jr $ra
partition: # [int, int] (int *array, int low, int high)
add $t0, $a0, $a2 # t0 = &array[pivot] => pivot = high
lb $t1, 0($t0) # t1 = array[pivot]
add $t2, $a0, $a1 # t2 => left = &array[low]
add $t3, $a0, $a1 # t3 => right = &array[low]
addi $t0, $t0, 1 # t4 => bound + 1 = &array[high + 1]
while: # while (right <= bound)
lb $t5, 0($t3) # t5 = array[right]
slt $t9, $t3, $t0 # check right < bound + 1
beq $t9, $zero, endPart
ifLess:
slt $t9, $t5, $t1 # check array[right] < array[pivot]
beq $t9, $zero, ifGreater
# swap (array[left], array[right])
lb $t6, 0($t2) # t6 = array[left]
sb $t5, 0($t2)
sb $t6, 0($t3)
addi $t2, $t2, 1 # left++
addi $t3, $t3, 1 # right++
j while
ifGreater:
slt $t9, $t1, $t5 # check array[right] > array[pivot]
beq $t9, $zero, ifEqual
addi $t0, $t0, -1 # bound--
# swap(array[right], array[bound])
lb $t6, 0($t0) # t6 = array[bound]
sb $t5, 0($t0)
sb $t6, 0($t3)
j while
ifEqual:
addi $t3, $t3, 1 # right++
j while
endPart:
sub $s0, $t2, $a0 # return left
sub $s1, $t3, $a0 # return right
jr $ra
############## Binary Search Implementation ##############
bSearch: # void (int *array, int low, int high, int x)
slt $t9, $a2, $a1 # check low >= high
bne $t9, $zero, bExit # if (high < low) exit
add $t0, $a1, $a2 # t0 = low + high
div $t0, $t8 # t0 = (low + high) / 2
mflo $t0
add $t1, $a0, $t0 # t1 => index = &array[pivot]
lb $t2, 0($t1) # t2 = array[index]
beq $t2, $a3, bReturn # if (array[index] == x) return index
slt $t9, $a3, $t2 # if (x < array[index])
bne $t9, $zero, searchLeft
searchRight:
addi $a1, $t0, 1 # new low = index + 1
j bSearch # call bSearch(&array, index + 1, high, x)
searchLeft:
addi $a2, $t0, -1 # new high = index - 1
j bSearch # call bSearch (&array, low, index - 1, x)
bReturn:
sub $t1, $t1, $a0 # calculate the final index of x
addi $t1, $t1, 1 # + 1 to be in range [1,40.000]
sw $t1, 0($s7) # overwrite index at POS
jr $ra # return the index of x in array
bExit:
jr $ra # x not found, return without any further action
.data
POS: .word 0 # Binary search result
array: # 40.000 1-byte positive integers [1,127]
.byte ##### PASTE YOUR DATASET HERE #############################################