Let ilselect(A, n, i) be an algorithm that selects the i-smallest from an array

Question

Let ilselect(A, n, i) be an algorithm that selects the i-smallest from an array A with n integers. It works as follows:
ilselect(A, n, i)
{
   r=partition(A, 1, n);
   //test if A[r] is the element to be selected if i == r, return A[r];
   //test if quickselect from the low-part
   if i < r, return quickselect(A, 1, r ? 1, i);
   //test if linearselect from the high-part
   if i > r, return linearselect(A, r + 1, n, i ? r);
}
That is, the algorithm runs quickselect on the low-part or runs linear select on the high-part. Show the average-case time complexity of the algorithm.

Explanation / Answer

Quickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data in two based on the pivot, accordingly as less than or greater than the pivot. However, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.