1. (10 pts.) In class, we learned about Lomutos Partition algorithm. There is another algorithm for this problem called Hoare partition. You can find this algorithm in section 5.2 of the textbook, also attached to this assignment. First read through this algorithm and learn how it works.

(a) Use this algorithm to write an algorithm that given a string as an array of n English characters, rearranges the elements in the same array such that any character from a-to-n appear on the left side of the array followed by all characters from o-to-z on the right side. For example, if string=homeworkfour is given, one possible way to rearrange them is as follows: hfmekorwoour.

(b) What is the asymptotic running time of your algorithm?

2. (10 pts.) Sometimes in practice, we need to sort arrays that have a large number of duplicates. In such applications, we might be able to reduce the time for sorting the array. Modify the Quicksort and the Lomuto partition algorithms such that it partitions the array into three parts, one each for items with values smaller than, equal to, and larger than the pivot.

The partition algorithm needs to return two indices lt and gt that point to the first and last element of the equal segment respectively. You then need to call Quicksort recursively for Quicksort(A[l...lt1]) and Quicksort(A[gt+1... r]).