Write a MIPS program that uses an implementation of quick sort to sort an array of...

Free

60.1K

Verified Solution

Question

Programming

Write a MIPS program that uses an implementation of quick sortto sort an array of numbers (Translate the following code into(Mars Assembly language).
Quicksort Implementation - C
int partition(int arr [] , int left , int right) {
int i=left, j=right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr [ i ] < pivot)
i ++;
while (arr [ j ] > pivot)
j âˆ’âˆ’;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j]; arr[j] = tmp;
i ++;
j âˆ’âˆ’;
}
}
return i ;
}

void quickSort(int arr [] , int left , int right) {
int index = partition(arr, left , right);
if (left < index âˆ’ 1)
quickSort(arr , left , index âˆ’ 1);
if (index < right)
quickSort(arr , index , right );
}

Answer & Explanation Solved by verified expert

3.9 Ratings (607 Votes)

Here is the solution of your problem:

Translate C language to MIPS Program

partition:

Â Â Â Â Â Â Â Â daddiuÂ Â $sp,$sp,-48

Â Â Â Â Â Â Â Â sdÂ Â Â Â Â Â $fp,40($sp)

Â Â Â Â Â Â Â Â moveÂ Â Â Â $fp,$sp

Â Â Â Â Â Â Â Â sdÂ Â Â Â Â Â $4,16($fp)

Â Â Â Â Â Â Â Â moveÂ Â Â Â $3,$5

Â Â Â Â Â Â Â Â moveÂ Â Â Â $2,$6

Â Â Â Â Â Â Â Â sllÂ Â Â Â Â $3,$3,0

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $3,24($fp)

Â Â Â Â Â Â Â Â sllÂ Â Â Â Â $2,$2,0

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $2,28($fp)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,24($fp)

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $2,0($fp)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,28($fp)

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $2,4($fp)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $3,24($fp)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,28($fp)

Â Â Â Â Â Â Â Â adduÂ Â Â Â $2,$3,$2

Â Â Â Â Â Â Â Â srlÂ Â Â Â Â $3,$2,31

Â Â Â Â Â Â Â Â adduÂ Â Â Â $2,$3,$2

Â Â Â Â Â Â Â Â sraÂ Â Â Â Â $2,$2,1

Â Â Â Â Â Â Â Â dsllÂ Â Â Â $2,$2,2

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $3,16($fp)

Â Â Â Â Â Â Â Â dadduÂ Â Â $2,$3,$2

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,0($2)

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $2,8($fp)

Â Â Â Â Â Â Â Â bÂ Â Â Â Â Â Â .L2

Â Â Â Â Â Â Â Â nop

.L4:

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,0($fp)

Â Â Â Â Â Â Â Â addiuÂ Â Â $2,$2,1

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $2,0($fp)

.L3:

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,0($fp)

Â Â Â Â Â Â Â Â dsllÂ Â Â Â $2,$2,2

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $3,16($fp)

Â Â Â Â Â Â Â Â dadduÂ Â Â $2,$3,$2

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,0($2)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $3,8($fp)

Â Â Â Â Â Â Â Â sltÂ Â Â Â Â $2,$2,$3

Â Â Â Â Â Â Â Â bneÂ Â Â Â Â $2,$0,.L4

Â Â Â Â Â Â Â Â nop

Â Â Â Â Â Â Â Â bÂ Â Â Â Â Â Â .L5

Â Â Â Â Â Â Â Â nop

.L6:

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,4($fp)

Â Â Â Â Â Â Â Â addiuÂ Â Â $2,$2,-1

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $2,4($fp)

.L5:

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,4($fp)

Â Â Â Â Â Â Â Â dsllÂ Â Â Â $2,$2,2

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $3,16($fp)

Â Â Â Â Â Â Â Â dadduÂ Â Â $2,$3,$2

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,0($2)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $3,8($fp)

Â Â Â Â Â Â Â Â sltÂ Â Â Â Â $2,$3,$2

Â Â Â Â Â Â Â Â bneÂ Â Â Â Â $2,$0,.L6

Â Â Â Â Â Â Â Â nop

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $3,0($fp)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,4($fp)

Â Â Â Â Â Â Â Â sltÂ Â Â Â Â $2,$2,$3

Â Â Â Â Â Â Â Â bneÂ Â Â Â Â $2,$0,.L2

Â Â Â Â Â Â Â Â nop

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,0($fp)

Â Â Â Â Â Â Â Â dsllÂ Â Â Â $2,$2,2

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $3,16($fp)

Â Â Â Â Â Â Â Â dadduÂ Â Â $2,$3,$2

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,0($2)

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $2,12($fp)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,0($fp)

Â Â Â Â Â Â Â Â dsllÂ Â Â Â $2,$2,2

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $3,16($fp)

Â Â Â Â Â Â Â Â dadduÂ Â Â $2,$3,$2

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $3,4($fp)

Â Â Â Â Â Â Â Â dsllÂ Â Â Â $3,$3,2

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $4,16($fp)

Â Â Â Â Â Â Â Â dadduÂ Â Â $3,$4,$3

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $3,0($3)

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $3,0($2)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,4($fp)

Â Â Â Â Â Â Â Â dsllÂ Â Â Â $2,$2,2

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $3,16($fp)

Â Â Â Â Â Â Â Â dadduÂ Â Â $2,$3,$2

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $3,12($fp)

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $3,0($2)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,0($fp)

Â Â Â Â Â Â Â Â addiuÂ Â Â $2,$2,1

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $2,0($fp)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,4($fp)

Â Â Â Â Â Â Â Â addiuÂ Â Â $2,$2,-1

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $2,4($fp)

.L2:

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $3,0($fp)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,4($fp)

Â Â Â Â Â Â Â Â sltÂ Â Â Â Â $2,$2,$3

Â Â Â Â Â Â Â Â beqÂ Â Â Â Â $2,$0,.L3

Â Â Â Â Â Â Â Â nop

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,0($fp)

Â Â Â Â Â Â Â Â moveÂ Â Â Â $sp,$fp

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $fp,40($sp)

Â Â Â Â Â Â Â Â daddiuÂ Â $sp,$sp,48

Â Â Â Â Â Â Â Â jÂ Â Â Â Â Â Â $31

Â Â Â Â Â Â Â Â nop

quickSort:

Â Â Â Â Â Â Â Â daddiuÂ Â $sp,$sp,-64

Â Â Â Â Â Â Â Â sdÂ Â Â Â Â Â $31,56($sp)

Â Â Â Â Â Â Â Â sdÂ Â Â Â Â Â $fp,48($sp)

Â Â Â Â Â Â Â Â sdÂ Â Â Â Â Â $28,40($sp)

Â Â Â Â Â Â Â Â moveÂ Â Â Â $fp,$sp

Â Â Â Â Â Â Â Â luiÂ Â Â Â Â $28,%hi(%neg(%gp_rel(quickSort)))

Â Â Â Â Â Â Â Â dadduÂ Â Â $28,$28,$25

Â Â Â Â Â Â Â Â daddiuÂ Â $28,$28,%lo(%neg(%gp_rel(quickSort)))

Â Â Â Â Â Â Â Â sdÂ Â Â Â Â Â $4,16($fp)

Â Â Â Â Â Â Â Â moveÂ Â Â Â $3,$5

Â Â Â Â Â Â Â Â moveÂ Â Â Â $2,$6

Â Â Â Â Â Â Â Â sllÂ Â Â Â Â $3,$3,0

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $3,24($fp)

Â Â Â Â Â Â Â Â sllÂ Â Â Â Â $2,$2,0

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $2,28($fp)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $3,28($fp)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,24($fp)

Â Â Â Â Â Â Â Â moveÂ Â Â Â $6,$3

Â Â Â Â Â Â Â Â moveÂ Â Â Â $5,$2

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $4,16($fp)

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $2,%got_disp(partition)($28)

Â Â Â Â Â Â Â Â moveÂ Â Â Â $25,$2

Â Â Â Â Â Â Â Â nop

Â Â Â Â Â Â Â Â swÂ Â Â Â Â Â $2,0($fp)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,0($fp)

Â Â Â Â Â Â Â Â addiuÂ Â Â $2,$2,-1

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $3,24($fp)

Â Â Â Â Â Â Â Â sltÂ Â Â Â Â $2,$3,$2

Â Â Â Â Â Â Â Â beqÂ Â Â Â Â $2,$0,.L10

Â Â Â Â Â Â Â Â nop

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,0($fp)

Â Â Â Â Â Â Â Â addiuÂ Â Â $2,$2,-1

Â Â Â Â Â Â Â Â moveÂ Â Â Â $3,$2

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,24($fp)

Â Â Â Â Â Â Â Â moveÂ Â Â Â $6,$3

Â Â Â Â Â Â Â Â moveÂ Â Â Â $5,$2

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $4,16($fp)

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $2,%got_disp(quickSort)($28)

Â Â Â Â Â Â Â Â moveÂ Â Â Â $25,$2

Â Â Â Â Â Â Â Â nop

.L10:

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $3,0($fp)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,28($fp)

Â Â Â Â Â Â Â Â sltÂ Â Â Â Â $2,$3,$2

Â Â Â Â Â Â Â Â beqÂ Â Â Â Â $2,$0,.L12

Â Â Â Â Â Â Â Â nop

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $3,28($fp)

Â Â Â Â Â Â Â Â lwÂ Â Â Â Â Â $2,0($fp)

Â Â Â Â Â Â Â Â moveÂ Â Â Â $6,$3

Â Â Â Â Â Â Â Â moveÂ Â Â Â $5,$2

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $4,16($fp)

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $2,%got_disp(quickSort)($28)

Â Â Â Â Â Â Â Â moveÂ Â Â Â $25,$2

Â Â Â Â Â Â Â Â nop

.L12:

Â Â Â Â Â Â Â Â nop

Â Â Â Â Â Â Â Â moveÂ Â Â Â $sp,$fp

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $31,56($sp)

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $fp,48($sp)

Â Â Â Â Â Â Â Â ldÂ Â Â Â Â Â $28,40($sp)

Â Â Â Â Â Â Â Â daddiuÂ Â $sp,$sp,64

Â Â Â Â Â Â Â Â jÂ Â Â Â Â Â Â $31

Â Â Â Â Â Â Â Â nop

// happy coding :)

Get Answers to Unlimited Questions

Join us to gain access to millions of questions and expert answers. Enjoy exclusive benefits tailored just for you!

Membership Benefits:

Unlimited Question Access with detailed Answers
Zin AI - 3 Million Words
10 Dall-E 3 Images
20 Plot Generations
Conversation with Dialogue Memory
No Ads, Ever!
Access to Our Best AI Platform: Flex AI - Your personal assistant for all your inquiries!

Become a Member

Write a MIPS program that uses an implementation of quick sort to sort an array of...

Free

60.1K

Verified Solution

Question

Programming

Answer & Explanation Solved by verified expert

Get Answers to Unlimited Questions

Membership Benefits:

Other questions asked by students