Question

Write a MIPS assembly program that sorts an array using bubble sort translating the C code...

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; }

Homework Answers

Answer #1

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"

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Translate pseudocode (bubble sort) into MIPS A[0] holds the smallest value and A[size -1] holds the...
Translate pseudocode (bubble sort) into MIPS A[0] holds the smallest value and A[size -1] holds the largest value. int t = 0; for ( int i=0; i<size-1; i++ ) { for ( int j=0; j<size-1-i; j++ ) { if ( A[j] > A[j+1] ) { t = A[j+1]; A[j+1] = A[j]; A[j] = t; } } } ---------------------------------------------------------------------------------- PART 2 Translate pseudocode (binary search) into MIPS The array A has already been sorted due to part 1. A[0] holds the...
***C++ CODING*** Write a program for sorting a list of integers in ascending order using the...
***C++ CODING*** Write a program for sorting a list of integers in ascending order using the bubble sort algorithm. Requirements Implement the following functions: Implement a function called readData int *readData( )   The function returns a pointer that points to the locations with integers reading from the file data.txt. arr is a pointer for storing the integers. The function returns the number of integers. The function readData reads the list of integers from a file call data.txt into the array...
Java : Modify the selection sort algorithm to sort an array of integers in descending order....
Java : Modify the selection sort algorithm to sort an array of integers in descending order. describe how the skills you have gained could be applied in the field. Please don't use an already answered solution from chegg. I've unfortunately had that happen at many occasion ....... ........ sec01/SelectionSortDemo.java import java.util.Arrays; /** This program demonstrates the selection sort algorithm by sorting an array that is filled with random numbers. */ public class SelectionSortDemo { public static void main(String[] args) {...
*****C++ program***** Please implement the following, comments throughout code to explain, and provide screenshots of output...
*****C++ program***** Please implement the following, comments throughout code to explain, and provide screenshots of output for proof. Write a program for sorting a list of integers in ascending order using the bubble sort algorithm. Implement the following functions: Implement a function called readData int readData( int *arr) arr is a pointer for storing the integers. The function returns the number of integers. The function readData reads the list of integers from a file call data.txt into the array arr....
This is my code and can you please tell me why it's not working? By the...
This is my code and can you please tell me why it's not working? By the way, it will work if I reduce 10,000,000 to 1,000,000. #include <iostream> using namespace std; void radixSort(int*a, int n) { int intBitSize = sizeof(int)<<3; int radix = 256; int mask = radix-1; int maskBitLength = 8;    int *result = new int[n](); int *buckets = new int[radix](); int *startIndex = new int[radix]();    int flag = 0; int key = 0; bool hasNeg =...
Write a Java program that asks the user to enter an array of integers in the...
Write a Java program that asks the user to enter an array of integers in the main method. The program should prompt the user for the number of elements in the array and then the elements of the array. The program should then call a method named isSorted that accepts an array of and returns true if the list is in sorted (increasing) order and false otherwise. For example, if arrays named arr1 and arr2 store [10, 20, 30, 41,...
in C++ Need a heap-sort function #include <iostream> #include <stdlib.h> #include <string> using namespace std; void...
in C++ Need a heap-sort function #include <iostream> #include <stdlib.h> #include <string> using namespace std; void MyFunc ( int *array ) { // Your code here ----------------- } int main(int argc,char **argv) { int *Sequence; int arraySize; // Get the size of the sequence cin >> arraySize; // Allocate enough memory to store "arraySize" integers Sequence = new int[arraySize];    // Read in the sequence for ( int i=0; i<arraySize; i++ ) cin >> Sequence[i]; // Run your algorithms to...
Quick sort func in C++ #include <iostream> #include <stdlib.h> #include <string> using namespace std; void MyFunc...
Quick sort func in C++ #include <iostream> #include <stdlib.h> #include <string> using namespace std; void MyFunc ( int *array ) { // Code here } int main(int argc,char **argv) { int *Sequence; int arraySize; // Get the size of the sequence cin >> arraySize; // Allocate enough memory to store "arraySize" integers Sequence = new int[arraySize];    // Read in the sequence for ( int i=0; i<arraySize; i++ ) cin >> Sequence[i]; // Run your algorithms to manipulate the elements...
Write the following program in MIPS: a) declare an array A of the following numbers: 3,...
Write the following program in MIPS: a) declare an array A of the following numbers: 3, 5, 8, 10, 12, 2, 76, 43, 90, 44 b) declare a variable called size which stores the number of element in array A, that is 10. c) write a subroutine to search for a number stored in an array and return true or false. In C++ the subroutine is as follows: search(array, size, number_To_Search) e.g. search(A, 10, 12) The subroutine should return 0...
Write a Java program that sorts an array of “Student” in an aescending order of their...
Write a Java program that sorts an array of “Student” in an aescending order of their “last names”. The program should be able to apply (bubble sort): Student [] studs = new Student[8]; s[0] = new Student("Saoud", "Mohamed", 3.61); s[1] = new Student("Abdelkader", "Farouk", 2.83); s[2] = new Student("Beshr" , "Alsharqawy", 1.99); s[3] = new Student("Nader", "Salah", 3.02); s[4] = new Student("Basem", "Hawary", 2.65); s[5] = new Student("Abdullah", "Babaker", 2.88); s[6] = new Student("Abdelaal", "Khairy", 3.13); s[7] = new Student("Mohamedain",...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT