Reference no: EM13754800

Recursive Quicksort

Write a MIPS program that uses a recursive implementation of quick sort to sort an array of numbers. The values of the array will be given to you via standard input. The first number will be the number of elements in the array and followed by the elements of the array in order. You can assume that there will be no more than 20 numbers and each number will fit in a signed 4 byte integer. After sorting the numbers, you should write them to standard out in increasing order. Your code should be able to handle an array with numbers that have the same value. You must use the C implementation of quick sort listed at the end of this assignment description as the basis for your MIPS implementation.

Sample Input and Output (User input in bold.)

Enter the number of elements in the array: 7

Enter the array elements: 2 5 1 -7 2 4 16

The elements sorted in ascending order are: -7 1 2 2 4 5 16

Submission Details

You will submit the assembly code in a file named quicksort .asm to the Assignment 4 dropbox on D2L. You may work in pairs on this assignment. Be sure to put both names in the comments at the top of the file.

Grading Guidelines

You will be graded on the functionality of the program and adherence to the directions. You must also adhere to the style guide given in class.

Quicksort Implementation - C

hit partition (int arr (J , int left , int right) { int i = left , j = right;

int tmp;

int pivot = arr(( left + right) / 2J;

while (1c=j) {

while (arr < pivot)

i++;

while (argil > pivot) --;

if (i <= J) {

tmp = arr Iii;

arriij = anLi ];

arr (J J = trap;

+-F; j --;

}
}

return i;

}

void quickSort(int arr (J , hit left , int right) { hit index = partition(arr, , left , right);

if (left < index - 1)

quickSort(arr, , left , index - 1);

if (index < right)

quickSort(arr, , index , right );

}