Experiment 2: MIPS Assembly Language Programming: Recursion
HELP NOTES
if | S | < Q then sort S and return the k-th element
else subdivide S into subsequences of Q elements each end if.
Use any sort routine. The routine should have at least two parameters: base address of the
array and size.
NOTES:
is the number of subsequences generated. You must round up the result of the
division | S | / Q. For example, if | S | =22 and Q=5 the number of subsequences will be , where ⌈ • ⌉ is the ceiling operator.
You can implement any algorithm for sorting: Insertion sort, Selection sort, Bubble sort, Shell sort, Merge sort, Heapsort, Quicksort, etc. However, choose a simple implementation (e.g.: Insertion). See their description at http://www.itl.nist.gov/div897/sqg/dads/HTML/sort.html
and relevant animations at http://www.sorting-algorithms.com/.
The median for a given list of numbers is found as follows: Sort these numbers either in
increasing or decreasing order, and then identify the number in the middle of this ordered
sequence. If the original list has odd SIZE, then the median is the [(SIZE+1)/2]-th
element in the ordered sequence. If the original list has even SIZE, then the median is the
arithmetic average of the two numbers in the middle of the ordered sequence, that is:
median={(value of the [SIZE/2]-th element)+ (value of the [(SIZE+2)/2]-th element)}/2.
Examples: If the sorted sequence is {S0, S1, S2, S3, S4}, then Median = S2;.
For the sorted sequence {S0, S1, S2, S3, S4, S5}, Median = (S2+S3) / 2.
For the sake of simplicity in this experiment, for the even SIZE case choose as the
median the number at offset SIZE/2 of the ordered sequence.
Sort each subsequence and determine its median. (See above discussion)
The sequence S will look like below:
Call SELECT recursively to find m, the median of the medians found in 2.
Before you call the SELECT procedure, you had better make some data manipulations on
sequence S.
Now you can call the SELECT procedure on the Sm sequence.
Create three subsequences S1, S2, and S3 to contain elements of S smaller than, equal to, and
larger than m, respectively.
To create these three sequences use a temporary array S’ (NOT used between recursive calls of SELECT procedure; this array is used only inside one SELECT procedure). Copy S elements in S’ (S’ is an image of S) and then implement the procedure shown in the figure below.
4.1 if | S1| ≥ k then call SELECT recursively to find the k-th element of S1
else if | S1| + | S2| ≥ k then return m
else call SELECT recursively to find the (k - | S1| - | S2|)-th element of S3 end if
end if.
subsequences of Q elements each
is the number of subsequences generated. You must round up the result of the
division | S | / Q. For example, if | S | =22 and Q=5 the number of subsequences will be 
, where ⌈ • ⌉ is the ceiling operator.
