The question is stated as follows:
A student was asked to sort a list of n numbers in decreasing order. The student writes an algorithm that works iteratively as follows. In every iteration, the following two steps are done:
Linear search is used to find the maximum element in the portion of the array which is not yet sorted.
The maximum element found in step 1 is placed at the beginning of the not-yet-sorted portion of the array.
This algorithm is given as input a list already sorted in descending order. What would be the time complexity of the algorithm on this input? Explain.
The algorithm described by the student is a variant of the selection sort algorithm, adapted to sort in decreasing order. To understand its time complexity when given a list that is already sorted in descending order, let's analyze the steps involved.
In the first iteration, the algorithm searches through the entire list of đn elements to find the maximum, which is the first element (since the list is already sorted in descending order). In the second iteration, the algorithm searches through the remaining nâ1 elements. This continues until the last iteration, where only one element is left.
Since the list is already sorted, the maximum element found in each iteration is already in its correct position. Thus, the placement step involves no movement or change in the list.
Even though the input list is already sorted in descending order, the algorithm still performs a linear search for the maximum element in each iteration. Therefore, the time complexity remains O(n²) This inefficiency arises because the algorithm does not take advantage of the already sorted order and continues to perform redundant searches.