(a) Box 1 shows the array quick-sort algorithm. Illustrate its behaviour as it sorts the following array of numbers: 0 1 2 3 4 5 6 7 8 9 91|71 29 43 97 59 17 93 61 13 Your illustration must show the contents of the array, and the value of p, after step 1.1, after step 1.2, and after step 1.3. Assume that step 1.1 takes a[left] as the pivot, and does not reorder the elements it puts into the left and right sub-arrays. [Unseen problem] 0 1 2 3 4 5 6 7 8 9 After step 1.1: 71 29 43 59 17 61 13 91 97 93 P 7 After step 1.2: 13 17 29 43 59 61 71 91 97 93 P 7 After step 1.3: 13 17 29 43 59 61 71 91 93 97 P 7 [-1 mark for each conceptual error.] [4] (b) Let comps(n) be the number of comparisons performed by the algorithm when sorting an array of n components. Assume that step 1.1 performs n-1 comparisons. Write down equations defining comps(n) when n1 and when n> 1: (i) in the best case, and (ii) in the worst case. Write down the time complexity of the quick-sort algorithm: (i) in the best case, and (ii) in the worst case. When does the best case arise? When does the worst case arise? [Notes] (i) Best case: comps(n) = = 1 comps(n) =2comps(n/2)+n-1 if n1 if n > 1 and the time complexity is O(n log n). This arises when the pivot is always the median of the elements in the array. (c) [1 mark for equations + 1 mark for complexity + 0.5 mark for explanation] (ii) Worst case: comps(n) = 1 comps(n) = comps(n-1)+n-1 if n1 if n>1 and the time complexity is O(n). This arises when the pivot is always the least or greatest of the elements in the array, i.e., when the array is already sorted! [1 mark for equations + 1 mark for complexity + 0.5 mark for explanation] [5] Write down the array merge-sort algorithm. Assume that an array merging algorithm is already available. [Notes] To sort a[left...right]: 1. If left < right: 1.1. Set m (left + right)/2. 1.2. Sort a[left...m]. 1.3. Sort a[m+1...right]. 1.4. Merge a[left...m] and a[m+1...right] into an auxiliary array. b. 1.5. Copy b into a[left...right]. 2. Terminate. -1 mark for each conceptual error.] [5] (d) Compare the quick-sort and merge-sort algorithms in terms of their time and space complexity. Which is better in terms of time complexity? Which is better in terms of space complexity? [Notes] Merge-sort's time complexity is guaranteed O(n log n), so it is faster than quick- sort for some inputs. [3 marks] Merge-sort's space complexity is O(n), since it needs an auxiliary array. Quick- sort's space complexity is O(log n) in the best case and O(n) in the worst case, since it only requires extra space for recursion. So merge-sort takes more space for some inputs. [3 marks] [6] [total 20]