Let us consider the easiest sorting algorithms Maxsort.

It works as follows: Find the largest key, say max, in the unsorted section of array (initially the whole array) and then interchange max with the element in the last position in the unsorted section. Now max is considered part of the sorted section consisting of larger keys at the end of the array. It is no longer in the unsorted section. Repeat this until the whole array is sorted.

a) Write an algorithm for Maxsort assuming an array E contains n elements to be sorted,

with indexes 0, 1,,n-1.

b) How many comparisons of keys does Maxsort do in the worst case and on average?

Submit source code in Java, test cases, results, and the answers to part (a) and (b).