Let ilselect(A, n, i) be an algorithm that selects the i-smallest from an array
ID: 3563544 • Letter: L
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 worst-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
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.