Consider the following strategy for choosing a pivot element for quicksort of an

Question

Consider the following strategy for choosing a pivot element for quicksort of an array A:

(for part A: https://www.chegg.com/homework-help/questions-and-answers/consider-following-strategy-choosing-pivot-element-quicksort-array-q10552011)

1. Let n be the number of elements of the array A 2. If n 15: (a) choose 2lVnl elements at random from n, let S be the new list with the chosen elements. (b) Sort the list S using insertion sort and use the median m of S as a pivot element. (c) Partition using m as a pivot. (d) Carry out quicksort recursively on the two parts

Explanation / Answer

To sort an array of size n it takes O(n^2) using insertion sort. Since size of S is sqrt(n),

So, to sort S it takes O(n) time. To find median in sorted array, it takes : O(1) time because we have

size of sorted part.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---