O Consider a list L of n elements where the first third of elements are sorted...

 

Transcribed Image Text:

O Consider a list L of n elements where the first third of elements are sorted in ascending order, the second third is sorted in de- scending order, and the last third is sorted in ascending order. For instance [1,5,7,10,4,2,3,9,12] is such a list. Our goal is to sort this list in descending order. • What is the maximum number of inversions in such lists? Argue why. ● Write an algorithm that returns the median of L in O(log1.5 n). The median is the middle element of the sorted list, i.e., L'[n/2] where L' is the list L that is sorted. • In the worst case, how many comparisons each one the following sorting algorithms performs to sort such lists: (i) insertion sort, (ii) quick sort where we use the median as the pivot, and (iii) counting sort. Window O Consider a list L of n elements where the first third of elements are sorted in ascending order, the second third is sorted in de- scending order, and the last third is sorted in ascending order. For instance [1,5,7,10,4,2,3,9,12] is such a list. Our goal is to sort this list in descending order. • What is the maximum number of inversions in such lists? Argue why. ● Write an algorithm that returns the median of L in O(log1.5 n). The median is the middle element of the sorted list, i.e., L'[n/2] where L' is the list L that is sorted. • In the worst case, how many comparisons each one the following sorting algorithms performs to sort such lists: (i) insertion sort, (ii) quick sort where we use the median as the pivot, and (iii) counting sort. Window

Answer rating: 100% (QA)

The image consists of text presenting a problem statement and series of questions related to sorting a specific type of list I will provide answers to each of the points raised in the problem statemen... View the full answer