Question

Write a MIPS assembly program that sorts a sequence of positive integers

entered from the console (one number in one line). The end of the

sequence is indicated by a 0 (zero). Verify that the program is correct by

simulation. You can use any sorting algorithm in your code except bubble

sort, such as selection sort, merge sort, quick sort, etc. There must be a

procedure call as well as looping in your code. use recursive procedure

calls instead of looping to solve the same problem. Describe your sorting

algorithm

Answer 1

# This sorting algorithm using selectoin sorting methode

.data
msg1: .asciiz "The elements sorted in ascending order are:" #output message
.align 2
space: .asciiz " "
.align 2
comma: .asciiz ","
.align 2
arr: .space 80
.text
MAIN:   

# Ask for user input and put value in $s1

addi $v0, $zero, 5 # call service 5 for integer input you can change the number as required
syscall # read integer
add $s1, $zero, $v0 # Save $t0 = len

# Load address for arr
la $s0, arr # Pointer to arr goes in $t1

add $a0, $zero, $s0 # Save arr pointer to $a0
add $a1, $zero, $s1 # Save len to $a1
# Ask for user input to fill arr
jal FILL

# Sort the list using selection sort
jal SORT

# Print list
jal PRINT

# Call to end program
addi $v0, $zero, 10 # system call for exit
syscall

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

FILL: # deal with stack and save
addi $t0, $zero, 0 # $t0 = counter = 0

FILL_LOOP:
slt $t1, $t0, $a1 # if(counter < len) continue
beq $t1, $zero, FILL_RETURN # if(counter >= len) branch out of loop

addi $v0, $zero 5 # call service 5 for integer input
syscall # read integer

addi $t2, $zero, 0 # clear $t2 and set to 0
add $t2, $zero, $v0 # $t2 holds input integer

add $t3, $zero, $t0 # $t3 = i
sll $t3, $t3, 2 # $t3 = counter * 4
add $t3, $t3, $a0 # addr of arr[counter]
sw $t2, 0($t3) # store values in arr

addi $t0, $t0, 1 # counter = counter + 1

j FILL_LOOP

FILL_RETURN:
jr $ra # Return

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

SORT:
addi $sp, $sp, -28 # make space for variables
sw $a0, 0($sp) # store $a0 (arr)
sw $a1, 4($sp) # store $a1 (len)
sw $ra, 8($sp) # store return address
sw $s0, 12($sp) # store $s0 ( i )
sw $s1, 16($sp) # store $s1 ( j )
sw $s2, 20($sp) # store $s2 (tmp)
sw $s3, 24($sp) # store $s3 (minIndex)

addi $s0, $zero, 0 # i = 0
add $t0, $zero, $a1 # $t0 = len
addi $t0, $t0, -1 # $t0 = len - 1

FOR_1:
slt $t1, $s0, $t0 # i < $t0 = len - 1 continue
beq $t1, $zero, SORT_RETURN # if !(i < len - 1) branch out of loop

add $s3, $zero, $s0 # minIndex = i
addi $t1, $s0, 1 # $t1 = i + 1
add $s1, $zero, $t1 # j = $t1 = i + 1

FOR_2:
slt $t1, $s1, $a1 # j < len continue
beq $t1, $zero, IF_1 # if !(j < len) branch out of loop

IF_2: # "FIND MIN"

# get value at arr[ j ] store in $t3
add $t2, $zero, $s1 # calculate index $t2 = j
sll $t2, $t2, 2 # offset = $t2 * 4
add $t2, $t2, $a0 # add offset to base address
lw $t3, 0($t2) # load value at arr[ j ] into $t3

# get value at arr[minIndex] store in$t5
add $t4, $zero, $s3 # calculate index $t4 = minIndex
sll $t4, $t4, 2 # offset = $t4 * 4
add $t4, $t4, $a0 # add offset to base address
lw $t5, 0($t4) # load value at arr[minIndex] into $t5

slt $t1, $t3, $t5 # if(arr[ j ] < arr[minIndex]) continue
beq $t1, $zero, LOOP_2 # if !(arr[ j ] < arr[minIndex]) branch out of if stmt
add $s3, $zero, $s1 # minIndex = j

LOOP_2:
addi $s1, $s1, 1 # j++
j FOR_2

IF_1: # "SWAP"
beq $s3, $s0, LOOP_1 # if(minIndex == i) branch out of if stmt (jump to LOOP_1)

# tmp = arr[minIndex]
add $t2, $zero, $s3 # calculate index $t2 = minIndex
sll $t2, $t2, 2 # offset = $t2 * 4
add $t2, $t2, $a0 # add offset to base address
lw $s2, 0($t2) # $s2 = tmp = arr[minIndex]

# arr[minIndex] = arr[ i ]
add $t3, $zero, $s0 # calculate index $t3 = i
sll $t3, $t3, 2 # offset = $t2 * 4
add $t3, $t3, $a0 # add offset to base address
lw $t0, 0($t3) # $t0 = arr [ i ]

sw $t0, 0($t2) # store value at arr[ i ] in arr[minIndex]

# arr[ i ] = tmp
sw $s2, 0($t3) # store tmp value in arr[ i ]   

LOOP_1:
addi $s0, $s0, 1 # i++
j FOR_1

SORT_RETURN:
lw $a0, 0($sp) # Get $a0
lw $a1, 4($sp) # Get $a1
lw $ra, 8($sp) # Get return address
lw $s0, 12($sp) # Get $s0
lw $s1, 16($sp) # Get $s1
lw $s2, 20($sp) # Get $s2
lw $s3, 24($sp) # Get $s3
addi $sp, $sp 28 # Adjust stack pointer
jr $ra # Return

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

PRINT:
addi $t0, $zero, 0 # $t0 = counter = 0
add $t1, $zero, $a0 # $t1 = arr address pointer

# Print msg1
la $s3, msg1
add $a0, $zero, $s3 # put address of space in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string

# Print a space
la $s3, space
add $a0, $zero, $s3 # put address of space in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string

PRINT_LOOP:
slt $t2, $t0, $a1 # if(counter < len) continue
beq $t2, $zero, PRINT_RETURN # if(counter >= len) branch out of loop

add $t3, $zero, $t0 # $t3 = counter
sll $t3, $t3, 2 # $t3 = counter * 4
add $t3, $t3, $t1 # $t3 = addr of arr[counter]

lw $t4, 0($t3) # Load value to print
add $a0, $zero, $t4 # put address of $t4 in $a0 to print

addi $v0, $zero, 1 # call service 1 to print integer
syscall # print integer

# Check if last array element
# Skip printing comma and space
addi $t3, $a1, -1 # $t3 = len - 1
beq $t3, $t0, PRINT_RETURN # if(at least element)

# Print a comma
la $s3, comma
add $a0, $zero, $s3 # put address of space in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string

# Print a space
la $s3, space
add $a0, $zero, $s3 # put address of space in $a0 to print
addi $v0, $zero, 4 # call service 4 to print a string
syscall # print string

addi $t0, $t0, 1 # counter - counter + 1

j PRINT_LOOP

PRINT_RETURN:
jr $ra # Return