Correct Answer - Option 1 : (a, left_end, k) and (a + left_end + 1, n - left_end - 1, k - left_end - 1)
We have to find the kth smallest element.
Condition is : if (left_end + 1 > k)
If this condition is true it means kth smallest element is present of left side. So a recursive call is done to kth_smallest(a, left_end,k);
If condition becomes false and left_end+ 1 is not equal to k, then kth smallest element will be present of right side of array. So, a recrusive call will be done as :
Kth_smallest(a+left_end+1, n-left_end_1, k-left_end -1);
Example:
Consider an array of 10 numbers i.e. N= 10, k= 7
a= {5,4,3,2,1,7,6,10,9,8}
pivot = 5
Step 1: after partition array will be = {4,3,2,1,5,7,6,10,9,8}
Here, left_end = 4
if(left_end < k) //else condition is satisifed
so , (a+left_end+1, n-left_end_1, k-left_end -1);
it will become (a+5, 5, 3)
array a = {7, 6, 10, 9, 8}
pivot = 7
STEP 2: After partition ()
Array = {6,7,10, 9, 8}
Left_end = 1
if(Left_end + 1 < k) // else condition is satisfied
so, (a+2, 3, 1)
array a = {10, 9, 8}
pivot = 10
STEP 3: After partition ()
Array a = {9, 8, 10}
Left_end = 2
Again left_end + 1 > k // if condition satisified
So, (a, 2, 1)
Array a = {9, 8}
Pivot = 9
STEP 4:
Array = {8,9}
Left _ end = 1
Left_end +1 > k // if condition satisifed
So, (a,1,1)
Array = {8}
Pivot = 8
STEP 8: here, left_end = 0,
Left_end + 1 ==k , a[left_end ]= 8
At the end, it returns the left_end value.