Write a MIPS assembly program that sorts an array using bubble sort translating the C code int main(void) { int array[] = {10, 2, 7, 5, 15, 30, 8, 6}; // input array int arraySize = sizeof(array)/sizeof(array[0]); bool swapped = true; int j = 0; int tmp; while (swapped) { swapped = false; //Note : "j" , "arraySize - j" are optimizations to the bubble sort algorithm j++; // j= sorted elements int i=0; /* "arraySize - j" is used because after the first run of the array , the last element of the array will be sorted , so j=1 and now we have to sort arraySize-1 elements, then after the second run of the array the next to last element will be sorted so j=2 and now we have to sort arraySize-2 elements. */ for ( i = 0; i < arraySize - j; i++) { if (array[i] > array[i + 1]) { tmp = array[i]; array[i] = array[i + 1]; array[i + 1] = tmp; swapped = true; } } } int i=0; //print sorted array for(i=0; i < arraySize; i++){ printf("%d", array[i]); } return 0; }
Sorting is the process of arranging data in an ascending or descending order. This example will introduce an algorithm, the Bubble Sort, for sorting integer data in a array. Consider for example the following array containing integer values.
The sort is carried out in two loops. The inner loop passes once through the data comparing elements in the array and swapping them if they are not in the correct order. For example, element 0 (55) is compared to element 1 (27), and they are swapped since 55 > 27.
Next element 1 (now 55) is compared with element 2 (13), and they are swapped since 55 > 13.
This process continues until a complete pass has been made through the array. At the end of the inner loop the largest value of the array is at the end of the array, and in its correct position. The array would look as follows.
An outer loop now runs which repeats the inner loop, and the second largest value moves to the correct position, as shown below.
Repeating this outer loop for all elements results in the array being sorted in ascending order.
Pseudo code for this algorithm follws.
for (int i = 0; i < size-1; i++)
{
for (int j = 0; j < ((size-1)-i); j++)
{
if (data[j] > data[j+1])
{
swap(data, j, j+1)
}
}
}
swap(data, i, j)
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
Bubble Sort in MIPS assembly
The following assembly program implements the Bubble Sort matching the pseudo code algorithm in the previous section.
.text
.globl main
main:
la $a0, array_base
lw $a1, array_size
jal PrintIntArray
la $a0, array_base
lw $a1, array_size
jal BubbleSort
jal PrintNewLine
la $a0, array_base
lw $a1, array_size
jal PrintIntArray
jal Exit
.data array_size: .word 8
array_base:
.word 5
.word 27
.word 13
.word 5
.word 44
.word 32
.word 17
.word 36
.text
# Subprogram: Bubble Sort
# Purpose: Sort data using a Bubble Sort algorithm
# Input Params: $a0 - array
# $a1 - array size
# Register conventions:
# $s0 - array base
# $s1 - array size
# $s2 - outer loop counter
# $s3 - inner loop counter
BubbleSort:
addi $sp, $sp -20 # save stack information
sw $ra, 0($sp)
sw $s0, 4($sp) # need to keep and restore save registers
sw $s1, 8($sp)
sw $s2, 12($sp)
sw $s3, 16($sp)
move $s0, $a0
move $s1, $a1
addi $s2, $zero, 0 #outer loop counter
OuterLoop:
addi $t1, $s1, -1
slt $t0, $s2, $t1
beqz $t0, EndOuterLoop
addi $s3, $zero, 0 #inner loop counter
InnerLoop: addi $t1, $s1, -1
sub $t1, $t1, $s2
slt $t0, $s3, $t1
beqz $t0, EndInnerLoop
sll $t4, $s3, 2 # load data[j]. Note offset is 4 bytes
add $t5, $s0, $t4
lw $t2, 0($t5)
addi $t6, $t5, 4 # load data[j+1]
lw $t3, 0($t6)
sgt $t0, $t2, $t3
beqz $t0, NotGreater
move $a0, $s0
move $a1, $s3
addi $t0, $s3, 1
move $a2, $t0
jal Swap # t5 is &data[j], t6 is &data[j=1]
NotGreater:
addi $s3, $s3, 1
b InnerLoop
EndInnerLoop:
addi $s2, $s2, 1
b OuterLoop
EndOuterLoop:
lw $ra, 0($sp) #restore stack information
lw $s0, 4($sp)
lw $s1, 8($sp)
lw $s2, 12($sp)
lw $s3, 16($sp)
addi $sp, $sp 20
jr $ra
# Subprogram: swap
# Purpose: to swap values in an array of integers
# Input parameters:
#$a0 - the array containing elements to swap
# $a1 - index of element 1
# $a2 - index of elelemnt 2
# Side Effects: Array is changed to swap element 1 and 2
Swap:
sll $t0, $a1, 2 # calcualate address of element 1
add $t0, $a0, $t0
sll $t1, $a2, 2 # calculate address of element 2
add $t1, $a0, $t1
lw $t2, 0($t0) #swap elements
lw $t3, 0($t1)
sw $t2, 0($t1)
sw $t3, 0($t0)
jr $ra
# Subprogram:
PrintIntArray
# Purpose: print an array of ints
# inputs: $a0 - the base address of the array
# $a1 - the size of the array
# PrintIntArray:
addi $sp, $sp, -16 # Stack record
sw $ra, 0($sp)
sw $s0, 4($sp)
sw $s1, 8($sp)
sw $s2, 12($sp)
move $s0, $a0 # save the base of the array to $s0
# initialization for counter loop
# $s1 is the ending index of the loop
# $s2 is the loop counter
move $s1, $a1
move $s2, $zero
la $a0 open_bracket # print open bracket
jal PrintString
loop:
# check ending condition
sge $t0, $s2, $s1
bnez $t0, end_loop
sll $t0, $s2, 2 # Multiply the loop counter by
# by 4 to get offset (each element
# is 4 big).
add $t0, $t0, $s0 # address of next array element
lw $a1, 0($t0) # Next array element
la $a0, comma
jal PrintInt # print the integer from array
addi $s2, $s2, 1 #increment $s0
b loop
end_loop:
li $v0, 4 # print close bracket
la $a0, close_bracket
syscall
lw $ra, 0($sp)
lw $s0, 4($sp)
lw $s1, 8($sp)
lw $s2, 12($sp) # restore stack and return
addi $sp, $sp, 16
jr $ra
.data
open_bracket: .asciiz "["
close_bracket: .asciiz "]"
comma: .asciiz ","
.include "utils.asm"
Get Answers For Free
Most questions answered within 1 hours.