Question

1. Recursion(Recursion (Recursion)) (16 points)

Consider the following algorithm, RecMaxSort, which sorts a list of integers:
procedure Rec MaxSort (a1, a2,...,an: list of integers L)
if (n < 2) return L
2. marinder = 1
3. for (i = 2 to n)
4. if (a[ i ] > a [ marIndex ] ) maxIndex = i
5. swap a [ mar Index] and a[n]
6. return RecMaxSort(a1, a2,..... an-1) o an
(a) (10 points) Prove that RecMaxSort correctly sorts a list of integers.
(b) (6 points) Let T(n) be the runtime of your algorithm for an input of size n. Write a recurrence for the runtime in terms of T(n) and use unraveling to find the asymptotic runtime in Big-θ notation. (Note that swap is θ(1))

Answer 1

The RecMaxSort algorithm correctly sorts a list of integers by recursively finding the index of the maximum element and swapping it with the last element.

Step-by-step explanation:

The RecMaxSort algorithm correctly sorts a list of integers. It does this by recursively finding the index of the maximum element in the list and swapping it with the last element. Then, it recursively sorts the remaining sublist.

To prove correctness, we can use mathematical induction. For the base case when the list has less than 2 elements, the algorithm returns the list unchanged, which is already sorted. For the induction step, assuming the algorithm sorts a sublist of size n-1 correctly, we can show that it also sorts a list of size n correctly by using the same approach as the base case but with the last element removed.

The runtime of the algorithm can be expressed by a recurrence relation. Let T(n) be the runtime for a list of size n. In each recursive call, the algorithm processes n-1 elements and performs a constant time operation in the swap. Therefore, the recurrence relation is T(n) = T(n-1) + Θ(1). Using unraveling technique, we can find that T(n) = Θ(n^2), which represents the quadratic asymptotic runtime of the algorithm.