This algorithm has two base cases. Explain what the first base case that the alg
ID: 3801832 • Letter: T
Question
This algorithm has two base cases. Explain what the first base case that the algorithm checks for: (see pictures)
2. (22 points) Quicksort Quicksort can be modified to obtain an elegant and efficient linear (O(n)) algorithm QuickSelect for the selection problem. Quick select (A, p, r, k) Hp & r-starting and ending indexes; to find k-th smallest number in non-empty array A; 1sks(r-p+1) 1 if p r then return Alp] else 2 q Partition (A,p,r) 3 pivot Distance q-p+1 4 f k pivot Distance then return Ala] 6 else if pivotDistance then return Quickselect (Arp,q-1,k) else return Quickselect(A,q+1,r, k-pivotDistance) input A-10, 3, 9, 4, 8, 5, 7, 6], p 1, r 8, k 2.Explanation / Answer
B)
First base case:
if(p == r)
return A[p];
When the starting and ending indexes in the quick select are same then kth smallest number is nothing but the value at the starting index(i.e ending also) A[p]. We just return the A[p]
T(First base case) = 1;
2) Second base case:
else
q = partition(a,p,r);
pivotDistance = q-p+1
if(k==pivotDistance)
return A[q];
if the pivotElement itself is the kth smallest number then we can return the value at the pivot index in the Array. i.e A[q].
T(second base case) = 20n + 6
3) not best case
else
q = partition(a,p,r);
pivotDistance = q-p+1
else if(k<pivotDistance) then
return quickselect(A,p,q-1,k)
else
return quickSelect(A,q+1,r,k-pivotdistance)
If the kth smallest is not same as pivot element and p !=r , we have to iterate the partion in which kth smallest number exists. If the pivotdistance is greater than k then do quickselect in the first partition(p to q-1) otherwise in the 2nd parition (q+1, r).
worst case recurrance relation: worst case happens if the parition always divides the array with size m into 2 subgroups of sizes m-1, 0 and pivot element and we always search the m-1 parition in the next iteration
T(n) = T(n-1)+ 20n + 6
best case: best case happens if the parition divides an array of size m into 2 equal groups [m-1/2], [m-1/2], pivot element always.
T(n) = T((n-1)/2)+20n+6
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.