4.6.1. Exercise 1¶
binary_search in a way that it does not test the equality
fst arr.(mid) = k and does not exclude the middle element, but
rather considers it as a part of one of the recursively processed
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
array, such that
perm.(i) is the index in
arr of the entry
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
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