Answer Happy

Question 5# Without an indexing function, the Least element algorithm is: Input: Sequence (2n)ne{....f} CS and an ordering rule "<" for S Output: Reordering of (In) ne {o...f} so that Is ST; for i = s, ..., f. Initialise: mts, j + s +1. Loop: If j = f +1 stop. If I; <Im then mj. j; +1 Repeat Swap the values of , and Im. (a) Apply the above algorithm to (In)ne{1,..,8} PRACTICE, using alphabetical order. What is the resulting reordered sequence (In) ne{1,...,8}? (b) Now apply the algorithm to this reordered sequence, but only to the part (In)ne{2,8). (i.e. s = 2). Write out the whole of the newly reordered sequence (2n)ne{1,...,8). (c) You have now completed the first two iterations of the Selection sort algorithm applied to PRACTICE. Continue on with all the remaining iterations to complete the sorting of the letters of PRACTICE into alphabetical order. Make a table showing the original sequence and the reordered sequence after each iteration. (d) How many comparison operations, in total, are used to sort PRACTICE? (e) By contrast, how many comparison operations, in total, would be used to sort PRACTICE using the Merge sort algorithm? Carry out the Merge sort algorithm on PRACTICE to find out. Note that when the merge algorithm reaches the stage where one of its input lists is empty, it does not need any more comparisons to complete its task. (E.g., when two sorted sequences of length I are merged at most (21 – 1) comparisons are required. Also note that the formula r2" given in lectures is not applicable here because that counts 'transfer' operations, not comparison operations.