COMP1521 2020T3 Q9 · MIPS函数/递归

COMP1521 2020T3 Q9 · 9 marks · MIPS
知识点: MIPS函数/递归（MASM-F） · 次: 递归/指针/排序 · 难度: 进阶
Topic: MIPS functions & recursion · Source: https://cgi.cse.unsw.edu.au/~cs1521/26T1/resources/practice_exams.html

一句话 / Summary: 实现快速排序sort/partition/swap

You have been given 20t3final_q9.s ,
a MIPS assembler program which implements all but 3 functions of this C program.

// COMP1521 20T3 final exam Q9 C reference

#include <stdio.h>

void sort ( int n , int a []);
int partition ( int n , int a []);
void swap ( int x , int y );
void read_array ( int n , int a [ n ]);
void print_array ( int n , int a [ n ]);

int main ( void ) {
int size ;
scanf ( "%d" , & size );
int array [ size ];
read_array ( size , array );
sort ( size , array );
print_array ( size , array );
}

void sort ( int n , int a []) {
if ( n > 1 ) {
int p = partition ( n , a );
sort ( p , a );
sort ( n - ( p + 1 ), a + p + 1 );
}
}

int partition ( int n , int a []) {
int pivot_value = a [ n - 1 ];
int i = 0 ;
for ( int j = 0 ; j < n ; j ++ ) {
if ( a [ j ] < pivot_value ) {
swap ( & a [ i ], & a [ j ]);
i = i + 1 ;
}
}
swap ( & a [ i ], & a [ n - 1 ]);
return i ;
}

void swap ( int x , int y ) {
int temp = * x ;

• x = * y ;
• y = temp ;

}

void read_array ( int n , int a []) {
for ( int i = 0 ; i < n ; i ++ ) {
scanf ( "%d" , & a [ i ]);
}
}

void print_array ( int n , int a []) {
for ( int i = 0 ; i < n ; i ++ ) {
printf ( "%d " , a [ i ]);
}
printf ( " \n " );
}

The functions which have not been implemented are named sort , partition and swap .

Add MIPS instructions for the functions sort , partition and swap to 20t3final_q9.s .

There are comments in 20t3final_q9.s which indicate where the MIPS instructions should be added.

20t3final_q9.s should then be equivalent to the above C program.

For example:

1521 mipsy 20t3final_q9.s
3
15
18
9
9 15 18
1521 mipsy 20t3final_q9.s
4
19
4
81
1
1 4 19 81
1521 mipsy 20t3final_q9.s
5
9
4
8
1
7
1 4 7 8 9

You must implement functions sort , partition , and swap equivalent to the supplied C.

No marks will be given for implementing other functions.

No marks will be given for implementing other sorting algorithms.

No error checking is required.

DO NOT CHANGE the supplied code for main , read_array , and print_array .

You can assume the supplied code works.

🤖 Write MIPS (mipsy). Read n, then n integers. Print them sorted in ascending order, one per line. (Any correct sort is accepted.)

Verified on the sandbox AND cross-checked against an independent oracle.