Below program has a Bubble Sort algorithm written in Assembly. Change this to use Selection Sort instead.

Use the following data in your array: $4,8,2,13,3,7$

Sort the data in ascending order and print out the result. The following assembly program implements the Bubble Sort matching the pseudocode

algorithm in the previous section.

$.$text

$.$globl main

main:

la $a$0,$ array$\_$base

lw $a$1,$ array$\_$size

jal PrintIntArray

la $a$0,$ array$\_$base

lw $a$1,$ array$\_$size

jal BubbleSort

jal PrintNewLine

la $a$0,$ array$\_$base

lw $a$1,$ array$\_$size

jal PrintIntArray

jal Exit

$.$data

array$\_$size: $.$word $8$

array$\_$base:

$.$word $55$

$.$word $27$

$.$word $13$

$.$word $5$

$.$word $44$

$.$word $32$

$.$word $17$

$.$word $36$

# Subproram: Bubble Sort

# Purpose: Sort data using a Bubble Sort algorithm

# Input Params: $a$0-$ array

# $a$1-$ array size

# Register conventions:

# $s$0-$ array base

# $s$1-$ array size

# $s$2-$ outer loop counter

# $s$3-$ inner loop counter

$.$text

BubbleSort:

addi $sp$,$ $sp$,-20$ # save stack information

sw $ra$,0($$sp$)$

sw $s$0,4($$sp$)$ # need to keep and restore save registers

sw $s$1,8($$sp$)$

sw $s$2,12($$sp$)$

sw $s$3,16($$sp$)$

move $s$0,$ $a$0$

move $s$1,$ $a$1$

addi $s$2,$ $zero, $0$ #outer loop counter

OuterLoop:

addi $t$1,$ $s$1,-1$

slt $t$0,$ $s$2,$ $t$1$

beqz $t$0,$ EndOuterLoop

addi $s$3,$ $zero, $0$ #inner loop counter

InnerLoop:

addi $t$1,$ $s$1,-1$

sub $t$1,$ $t$1,$ $s$2$

slt $t$0,$ $s$3,$ $t$1$

beqz $t$0,$ EndInnerLoop

sll $t$4,$ $s$3,2$ # load data$[$j$].$ Note offset is $4$ bytes

add $t$5,$ $s$0,$ $t$4$

lw $t$2,0($$t$5)$

addi $t$6,$ $t$5,4$ # load data$[$j$+1]$

lw $t$3,0($$t$6)$

sgt $t$0,$ $t$2,$ $t$3$

beqz $t$0,$ NotGreater

move $a$0,$ $s$0$

move $a$1,$ $s$3$

addi $t$0,$ $s$3,1$

move $a$2,$ $t$0$

jal Swap # t$5$ is &data$[$j$],$ t$6$ is &data$[$j$+1]$

NotGreater:

addi $s$3,$ $s$3,1$

b InnerLoop

EndInnerLoop:

addi $s$2,$ $s$2,1$

b OuterLoop

EndOuterLoop:

lw $ra$,0($$sp$)$ #restore stack information

lw $s$0,4($$sp$)$

lw $s$1,8($$sp$)$

lw $s$2,12($$sp$)$

lw $s$3,16($$sp$)$

addi $sp$,$ $sp $20$

jr $ra

# Subprogram: swap

# Purpose: to swap values in an array of integers

# Input parameters: $a$0-$ the array containing elements to swap

# $a$1-$ index of element $1$

# $a$2-$ index of elelemnt $2$

# Side Effects: Array is changed to swap element $1$ and $2$

Swap:

sll $t$0,$ $a$1,2$ # calcualate address of element $1$

add $t$0,$ $a$0,$ $t$0$

sll $t$1,$ $a$2,2$ # calculate address of element $2$

add $t$1,$ $a$0,$ $t$1$

lw $t$2,0($$t$0)$ #swap elements

lw $t$3,0($$t$1)$

sw $t$2,0($$t$1)$

sw $t$3,0($$t$0)$

jr $ra

# Subprogram: PrintIntArray

# Purpose: print an array of ints

# inputs: $a$0-$ the base address of the array

# $a$1-$ the size of the array

#

PrintIntArray:

addi $sp$,$ $sp$,-16$ # Stack record

sw $ra$,0($$sp$)$

sw $s$0,4($$sp$)$

sw $s$1,8($$sp$)$

sw $s$2,12($$sp$)$

move $s$0,$ $a$0$ # save the base of the array to $s$0$

# Initialization for counter loop

# $s$1$ is the ending index of the loop

# $s$2$ is the loop counter

move $s$1,$ $a$1$

move $s$2,$ $zero

la $a$0,$ open$\_$bracket # print open bracket

jal PrintString

loop:

# check ending condition

sge $t$0,$ $s$2,$ $s$1$

bnez $t$0,$ end$\_$loop

sll $t$0,$ $s$2,2$ # Multiply the loop counter by

# by $4$ to get offset $($each element

$13$ INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING

# is $4$ big$).$

add $t$0,$ $t$0,$ $s$0$ # address of next array element

lw $a$1,0($$t$0)$ # Next array element

la $a$0,$ comma

jal PrintInt # print the integer from array

addi $s$2,$ $s$2,1$ #increment $s$0$

b loop

end$\_$loop:

li $v$0,4$ # print close bracket

la $a$0,$ close$\_$bracket

syscall

lw $ra$,0($$sp$)$

lw $s$0,4($$sp$)$

lw $s$1,8($$sp$)$

lw $s$2,12($$sp$)$ # restore stack and return

addi $sp$,$ $sp$,16$

jr $ra

$.$data

open$\_$bracket: $.$asciiz $"["$

close$\_$bracket: $.$asciiz $"]"$

comma: $.$asciiz $","$

$.$include "utils.asm"