4.6. Exercises
4.6.1. Exercise 1
Modify binary_search in a way that it does not test the equality
of fst arr.(mid) = k and does not exclude the middle element, but
rather considers it as a part of one of the recursively processed
array subparts.
4.6.2. Exercise 2
Implement a version of merge sort that splits the sub-arrays into three parts and then combines them together. Compare its performance to the ordinary 2-way merge sort.
4.6.3. Exercise 3
Develop and implement a version of merge sort that does not rearrange
the input array arr, but returns an array perm of type int
array, such that perm.(i) is the index in arr of the entry
with i th smallest key in the array.
4.6.4. Exercise 4
Implement and check the loop invariants (described in the text) of the
partition procedure from Section Partitioning an array, as well as
as the procedure’s postcondition. The assertions should relate the
initial array, the final array and returned i. You might need to
introduce an initial copy of an unmodified array to assert those
statements.
4.6.5. Exercise 5
Change the procedure partition from Section Partitioning an array
so it would take as pivot the first element of an array.
4.6.6. Exercise 6
Implement and check a precondition of the sort subrouting within
quick_sort from Section Partitioning an array. It should relate the
initial array, and the sub-arrays, obtained as results of
partitioning, stating something about the arrangement of elements in
them wrt. element at the position mid and others.
4.6.7. Exercise 7
Solve, by means of changing a variable, the following recurrence relation:
4.6.8. Exercise 8
What is the worst-case complexity of Quicksort? Obtain it by stating and solving the corresponding recurrence relations. Give an example of an array when the worst-case complexity is achieved (hint: think of a case insert sort does its best).
4.6.9. Exercise 9
Prove, out of definitions that for ay two functions \(f(n)\) and \(g(n)\), one has \(f(n) \in \Theta(g(n))\) if and only if \(f(n) \in O(g(n))\) and \(f(n) \in \Omega(g(n))\).
4.6.10. Exercise 10
Enhance A functor for sorting Sorting, so it would also take
an instance of a signature Printable that provides an
implementation for printing elements of an array. With that
Sorting should also feature a second version of sorting,
sort_print, which will print a sorting trace using the machinery
imported from Printable.