Name: Syed Sibgatullah
Student ID: 400156014
Computer Architecture Lab
Implementation and Execution of
MIPS Assembly Programs Using
QtSpim (Sorting Algorithms)
Objective
The objective of this work is to implement basic array-processing and sorting algorithms in MIPS
assembly language and verify their correctness through simulation.
Tools and Environment
• Architecture: MIPS32
• Simulator: QtSpim
• Input Method: Console-based user input
• Output Method: Console display (screenshots attached separately)
Methodology
For each program, the user provides the size of the array followed by its elements through the
console. Dynamic memory allocation is used to store the array. Each program processes the input
array according to its respective algorithm and displays the nal result on the console.
Input and Output
• Input:
◦ Array size (integer)
◦ Array elements (integers)
• Output:
◦ Maximum program: Displays the maximum element of the array
◦ Sorting programs: Display the sorted array in ascending order
fi
Results
All programs were successfully executed in QtSpim. The outputs obtained from the console
matched the expected results for different input cases. Console screenshots for each program
execution are included to demonstrate correct functionality.
1. Maximum Element in an Array
2. Bubble Sort
3. Insertion Sort
4. Selection Sort
Maximum:
# n = s0
# address_0 = s1
# maximum = s2
.text
main:
# Print "Enter the size of array: "
li $v0, 4
la $a0, prompt1
syscall
# Enter the size of array
li $v0, 5
syscall
# s0 = n
move $s0, $v0
# Create Array of size n
li $v0, 9
mul $a0, $s0, 4
syscall
# s1 = address_0
move $s1, $v0
# Print "Enter the elements of array:\n"
li $v0, 4
la $a0, prompt2
syscall
# t0 = 0
move $t0, $zero
# t1 = address_0
move $t1, $s1
# Enter the elements of array
input:
# Enter number
li $v0, 5
syscall
# array[i] = number
sw $v0, ($t1)
#i=i+1
addi $t0, $t0, 1
# Move to the next address
addi $t1, $t1, 4
# if i != n goto input
bne $t0, $s0, input
# t0 = 0
move $t0, $zero
# t1 = address_0
move $t1, $s1
# s2 = array[0]
lw $s2, ($t1)
# t9 = n - 1
addi $t9, $s0, -1
loop:
#i=i+1
addi $t0, $t0, 1
# Move to the next address
addi $t1, $t1, 4
# t2 = array[i+1]
lw $t2, ($t1)
# if array[i+1] > maximum goto swap
bgt $t2, $s2, swap
loop_continue:
# if i != n goto loop
bne $t0, $t9, loop
j nish
swap:
# s2 = t2
move $s2, $t2
j loop_continue
nish:
# Print "Maximum: "
li $v0, 4
la $a0, prompt3
syscall
# Print maximum
li $v0, 1
move $a0, $s2
syscall
jr $ra
.data
prompt1: .asciiz "Enter the size of array: "
prompt2: .asciiz "Enter the elements of array:\n"
prompt3: .asciiz "Maximum: “
fi
fi
Bubble Sort
.text
main:
# Print "Enter the size of array: "
li $v0, 4
la $a0, prompt1
syscall
# Enter the size of array
li $v0, 5
syscall
# s0 = n
move $s0, $v0
# Create Array of size n
li $v0, 9
mul $a0, $s0, 4
syscall
# s1 = address_0
move $s1, $v0
# Print "Enter the elements of array:\n"
li $v0, 4
la $a0, prompt2
syscall
# t0 = 0
move $t0, $zero
# t1 = address_0
move $t1, $s1
# Enter the elements of array
input:
# Enter number
li $v0, 5
syscall
# array[i] = number
sw $v0, ($t1)
#i=i+1
addi $t0, $t0, 1
# Move to the next address
addi $t1, $t1, 4
# if i != n goto input
bne $t0, $s0, input
next:
# t0 = 0
move $t0, $zero
# t1 = address_0
move $t1, $s1
# t9 = n - 1
addi $t9, $s0, -1
loop1:
# t2 = 0
move $t2, $zero
# t3 = address_0
move $t3, $s1
# s2 = swapped = 0
move $s2, $zero
loop2:
# t4 = array[j]
lw $t4, ($t3)
# t5 = array[j+1]
lw $t5, 4($t3)
# if array[j] > array[j+1] then swap(array[j], array[j+1])
bgt $t4, $t5, swap
loop2_continue:
#j=j+1
addi $t2, $t2, 1
# Move to the next address
addi $t3, $t3, 4
# if j != n - 1 goto loop2
bne $t2, $t9, loop2
loop1_continue:
# if swapped == 0 goto nish
beq $s2, $zero, nish
#i=i+1
addi $t0, $t0, 1
# Move to the next address
addi $t1, $t1, 4
# if i != n goto loop1
bne $t0, $s0, loop1
j nish
swap:
# swap(array[j], array[j+1])
sw $t4, 4($t3)
sw $t5, ($t3)
# s2 = swapped = 1
li $s2, 1
j loop2_continue
nish:
# Print "Sorted array:\n"
li $v0, 4
la $a0, prompt2
syscall
# t0 = 0
move $t0, $zero
# t1 = address_0
move $t1, $s1
# Print sorted array
print:
# Print array[i]
li $v0, 1
lw $a0, ($t1)
fi
fi
fi
fi
syscall
# Print comma
li $v0, 4
la $a0, comma
syscall
#i=i+1
addi $t0, $t0, 1
# Move to the next address
addi $t1, $t1, 4
# if i != n goto loop1
bne $t0, $s0, print
jr $ra
.data
prompt1: .asciiz "Enter the size of array: "
prompt2: .asciiz "Enter the elements of array:\n"
prompt3: .asciiz "Sorted array:\n"
comma: .asciiz ", "
Insertion Sort
.text
main:
li $v0, 4
la $a0, prompt1
syscall
li $v0, 5
syscall
# s0 = n
move $s0, $v0
# Create Array of size n
li $v0, 9
mul $a0, $s0, 4
syscall
# s1 = address_0
move $s1, $v0
li $v0, 4
la $a0, prompt2
syscall
# t0 = 0
move $t0, $zero
# t1 = address_0
move $t1, $s1
input:
li $v0, 5
syscall
sw $v0, ($t1)
addi $t0, $t0, 1
# Move to the next address
addi $t1, $t1, 4
bne $t0, $s0, input
next:
# t0 = 1
li $t0, 1
# t1 = address_1
addi $t1, $s1, 4
loop1:
# s2 = array[i]
lw $s2, ($t1)
# t2 = i
move $t2, $s0
# t3 = address_i
move $t3, $t1
# t4 = array[holeindex - 1]
lw $t4, -4($t3)
loop2:
# if holeindex == 0 goto loop1_continue
beq $t2, $zero, loop1_continue
# if array[holeindex - 1] == value_to_insert
beq $t4, $s2, loop1_continue
# if array[holeindex - 1] < value_to_insert
blt $t4, $s2, loop1_continue
# array[holeindex] = array[holeindex - 1]
sw $t4, ($t3)
# holeindex = holeindex - 1
addi $t2, $t2, -1
# holepos = holepos - 1
addi $t3, $t3, -4
# t4 = array[holeindex - 1]
lw $t4, -4($t3)
j loop2
loop1_continue:
# array[holeindex] = value_to_insert
sw $s2, ($t3)
#i=i+1
addi $t0, $t0, 1
# Move to the next address
addi $t1, $t1, 4
# if i != n goto loop1
bne $t0, $s0, loop1
nish:
# Print "Sorted array:\n"
li $v0, 4
la $a0, prompt2
syscall
fi
# t0 = 0
move $t0, $zero
# t1 = address_0
move $t1, $s1
# Print sorted array
print:
# Print array[i]
li $v0, 1
lw $a0, ($t1)
syscall
# Print comma
li $v0, 4
la $a0, comma
syscall
#i=i+1
addi $t0, $t0, 1
# Move to the next address
addi $t1, $t1, 4
# if i != n goto loop1
bne $t0, $s0, print
jr $ra
.data
prompt1: .asciiz "Enter the size of array: "
prompt2: .asciiz "Enter the elements of array:\n"
prompt3: .asciiz "Sorted array:\n"
comma: .asciiz ", "
Selection Sort
.text
main:
# Print "Enter the size of array: "
li $v0, 4
la $a0, prompt1
syscall
# Enter the size of array
li $v0, 5
syscall
# s0 = n
move $s0, $v0
# Create Array of size n
li $v0, 9
mul $a0, $s0, 4
syscall
# s1 = address_0
move $s1, $v0
# Print "Enter the elements of array:\n"
li $v0, 4
la $a0, prompt2
syscall
# t0 = 0
move $t0, $zero
# t1 = address_0
move $t1, $s1
# Enter the elements of array
input:
# Enter number
li $v0, 5
syscall
# array[i] = number
sw $v0, ($t1)
#i=i+1
addi $t0, $t0, 1
# Move to the next address
addi $t1, $t1, 4
# if i != n goto input
bne $t0, $s0, input
next:
# t0 = 0
move $t0, $zero
# t1 = address_0
move $t1, $s1
# t9 = n - 1
addi $t9, $s0, -1
for1:
# index_of_min = i
move $s2, $t0
#j=i+1
addi $t2, $t0, 1
# address_j = address_i + 4
addi $t3, $t1, 4
for2:
# t5 = array[j]
lw $t5, ($t3)
# t6 = array[min]
mul $t7, $s2, 4
add $t8, $s1, $t7
lw $t6, ($t8)
# if t5 < t6 then
blt $t5, $t6, swap
for2_continue:
#j=j+1
addi $t2, $t2, 1
# Move to the next address
addi $t3, $t3, 4
# if j != n goto for2
bne $t2, $s0, for2
j for1_continue
swap:
# s2 = t2
move $s2, $t2
j for2_continue
for1_continue:
# lw list[min]
mul $t7, $s2, 4
add $t8, $s1, $t7
# swap(list[min], list[i])
lw $t5, ($t8)
lw $t6, ($t1)
sw $t5, ($t1)
sw $t6, ($t8)
#i=i+1
addi $t0, $t0, 1
# Move to the next address
addi $t1, $t1, 4
# if i != n-1 goto for1
bne $t0, $t9, for1
j nish
nish:
# Print "Sorted array:\n"
li $v0, 4
la $a0, prompt2
syscall
# t0 = 0
move $t0, $zero
# t1 = address_0
move $t1, $s1
# Print sorted array
print:
# Print array[i]
li $v0, 1
lw $a0, ($t1)
syscall
# Print comma
li $v0, 4
la $a0, comma
syscall
#i=i+1
addi $t0, $t0, 1
# Move to the next address
addi $t1, $t1, 4
# if i != n goto loop1
bne $t0, $s0, print
fi
fi
jr $ra
.data
prompt1: .asciiz "Enter the size of array: "
prompt2: .asciiz "Enter the elements of array:\n"
prompt3: .asciiz "Sorted array:\n"
comma: .asciiz ", "